Background

Luogu’s testdata are for informal communication only and are not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

$A_1, A_2, \cdots , A_n$ is an array consisting of $n$ natural numbers (i.e., non-negative integers). Based on this, we use the array $B_1 \cdots B_n$ to represent the prefix maximums of $A$.

As shown above, $B_i$ is defined as the maximum value among the first $i$ numbers in array $A$. From this definition, it is easy to know that $A_1 = B_1$, and as $i$ increases, $B_i$ is monotonically non-decreasing. In addition, we use $\mathrm{sum} = A_1 + A_2 + \cdots + A_n$ to denote the total sum of the $n$ numbers in array $A$.

Now the array $B$ is given. We want to reconstruct array $A$ from the values of $B$. Obviously, for a given $B$, the values of $A$ may not be unique. Please compute, among all possible arrays $A$, what are the maximum and minimum possible values of $\mathrm{sum}$?

Input Format

Read from standard input.

The first line contains a positive integer $n$.

The second line contains $n$ natural numbers $B_1, B_2, \cdots , B_n$, separated by spaces.

Output Format

Write to standard output.

Output consists of two lines.

The first line outputs an integer, representing the maximum value of $\mathrm{sum}$.

The second line outputs an integer, representing the minimum value of $\mathrm{sum}$.

6
0 0 5 5 10 10

30
15

7
10 20 30 40 50 60 75

285
285

Hint

Sample 1 Explanation

Possible values of array $A$ include, but are not limited to, the following three cases.

Case 1: $A = [0, 0, 5, 5, 10, 10]$

Case 2: $A = [0, 0, 5, 3, 10, 4]$

Case 3: $A = [0, 0, 5, 0, 10, 0]$

Among them, in the first case $\mathrm{sum} = 30$ is the maximum value, and in the third case $\mathrm{sum} = 15$ is the minimum value.

Sample 2 Explanation

$A = [10, 20, 30, 40, 50, 60, 75]$ is the only possible value, so both the maximum and minimum values of $\mathrm{sum}$ are $285$.

Subtasks

$50\%$ of the testdata satisfy that array $B$ is strictly increasing, i.e., $0 < B_1 < B_2 < \cdots < B_n < 10^5$.

All testdata satisfy $n \leq 100$ and array $B$ is monotonically non-decreasing, i.e., $0 \leq B_1 \leq B_2 \leq \cdots \leq B_n \leq 10^5$.

Translated by ChatGPT 5