#P2021091. 数组推导

数组推导

数组推导

题目描述

题目描述

A1,A2,⋯,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的最大值和最小值分别是多少?

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数n。

输入的第二行包含n个用空格分隔的自然数B1,B2,⋯,Bn。

输出格式

输出到标准输出。

输出共两行。

第一行输出一个整数,表示sum的最大值。

第二行输出一个整数,表示sum的最小值。

数据范围

(原站未提供,导入后需人工补齐)

样例

6
0 0 5 5 10 10
30
15

样例1解释
数组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为最小值。
7
10 20 30 40 50 60 75
285
285
样例2解释
A=[10,20,30,40,50,60,75]是唯一可能的取值,所以sum的最大、最小值均为285。

提示

子任务

50%的测试数据满足数组B单调递增,即0<B1<B2<⋯<Bn<10^5;

全部的测试数据满足n≤100且数组B单调不降,即0≤B1≤B2≤⋯≤Bn≤10^5。