Migrated from Lutece 2969 A very easy problem of sequence

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You have been given an array $a$ consisting of $n$ positive integers, you need to construct an array $b$ with the same length, which satisfy the following conditions:

1. for each $i$: $b_i\leq a_i$;
2. there exist a position $k$ that for each $i$: $b_i\leq b_{i+1}$ when $1\leq i< k$ , and $b_i \ge b_{i+1}$ when $k\le i < n$ .

Please output the maximum sum of the array $b$.

Input

The first line contains an integer $n$. The second line contains $n$ positive integers $a_1,a_2,......,a_n$.

Output

One positive integer, the maximum sum of the array $b$.

Samples

6
1 1 4 5 1 4

13

Constraints

$1\le n \le 5\times 10^5$; $1\le a_i\le 10^9$.