1067: 数组推导
内存限制：256 MB
时间限制：1 S
评测方式：文本比较
命题人：外部导入
提交：63
解决：27
题目描述
A1,A2,A3,...,An是一个由n个自然数（即非负整数）组成的数组。在此基础上，我们用数组B1...Bn表示A的前缀最大值。
Bi=max{A1,A2,...,Ai}
如上所示，Bi定义为数组A中前i个数的最大值。
根据该定义易知A1=B1，且随着i的增大，Bi单调不降。
此外，我们用sum=A1+A2+...+An表示数组A中n个数的总和。
现已知数组B，我们想要根据B的值来反推数组A。
显然，对于给定的B，A的取值可能并不唯一。
试计算，在数组A所有可能的取值情况中，sum的最大值和最小值分别是多少？
Bi=max{A1,A2,...,Ai}
如上所示，Bi定义为数组A中前i个数的最大值。
根据该定义易知A1=B1，且随着i的增大，Bi单调不降。
此外，我们用sum=A1+A2+...+An表示数组A中n个数的总和。
现已知数组B，我们想要根据B的值来反推数组A。
显然，对于给定的B，A的取值可能并不唯一。
试计算，在数组A所有可能的取值情况中，sum的最大值和最小值分别是多少？
输入
从标准输入读入数据。
输入的第一行包含一个正整数n。
输入的第二行包含n个用空格分隔的自然数B1,B2,...,Bn。
输入的第一行包含一个正整数n。
输入的第二行包含n个用空格分隔的自然数B1,B2,...,Bn。
输出
输出到标准输出。
输出共两行。
第一行输出一个整数，表示sum的最大值。
第二行输出一个整数，表示sum的最小值。
输出共两行。
第一行输出一个整数，表示sum的最大值。
第二行输出一个整数，表示sum的最小值。
样例输入 复制
6
0 0 5 5 10 10样例输出 复制
30
15提示
数组 A 的可能取值包括但不限于以下三种情况。
情况一：A=[0,0,5,5,10,10]
情况二：A=[0,0,5,3,10,4]
情况三：A=[0,0,5,0,10,0]
其中第一种情况 sum=30 为最大值，第三种情况 sum=15 为最小值。