问题描述

$A_1,A_2,\dots,A_n$ 是一个由 $n$ 个自然数（即非负整数）组成的数组。

在此基础上，我们用数组 $B_1,\dots,B_n$ 表示 $A$ 的前缀最大值：

如上所示，$B_i$ 定义为数组 $A$ 中前 $i$ 个数的最大值。根据该定义易知 $A_1=B_1$，且随着 $i$ 的增大，$B_i$ 单调不降。

此外，我们用 $\text{sum}=A_1+A_2+\dots+A_n$ 表示数组 $A$ 中 $n$ 个数的总和。

现已知数组 $B$，我们想要根据 $B$ 的值来反推数组 $A$。

显然，对于给定的 $B$，$A$ 的取值可能并不唯一。试计算，在数组 $A$ 所有可能的取值情况中，$\text{sum}$ 的最大值和最小值分别是多少？

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个用空格分隔的自然数 $B_1,B_2,\dots,B_n$。

输出格式

输出共两行。

• 第一行输出一个整数，表示 $\text{sum}$ 的最大值。
• 第二行输出一个整数，表示 $\text{sum}$ 的最小值。

输入样例 1

6
0 0 5 5 10 10

输出样例 1

30
15

输入样例 2

7
10 20 30 40 50 60 75

输出样例 2

285
285

说明

样例 1 解释：

数组 $A$ 的可能取值包括但不限于以下三种情况：

• 情况一：$A=[0,0,5,5,10,10]$
• 情况二：$A=[0,0,5,3,10,4]$
• 情况三：$A=[0,0,5,0,10,0]$

其中第一种情况 $\text{sum}=30$ 为最大值，第三种情况 $\text{sum}=15$ 为最小值。

样例 2 解释：

$A=[10,20,30,40,50,60,75]$ 是唯一可能的取值，所以 $\text{sum}$ 的最大、最小值均为 285。

数据范围

• $50\%$ 的测试数据满足数组 $B$ 单调 严格 增加，即 $0 < B_1 < B_2 < \cdots < B_n < 10^5$。
• 全部的测试数据满足 $n \le 100$ 且数组 $B$ 单调不降，即 $0 \le B_1 \le B_2 \le \cdots \le B_n \le 10^5$。