Migrated from Lutece 1571 Deal W1th The Number

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

There is a sequence which contains $N$ numbers $x_1, x_2, \dots, x_N$.

Every time you can choose a number $x_i$, delete it from the sequence and you will gain $\min\{x_{i - 1}, x_{i + 1}\}$ scores. If $x_i$ is the first or last number in the sequence, you will gain $0$ scores.

After that, merge the left part and the right part of the rest of the numbers, they will form a new sequence with new indexes, and you can do the same operation on it.

What's the maximum sum scores you can gain at last?

Input

The first line contains an integer $N$.

The second line contains $N$ integers $x_1, x_2, \dots, x_N$.

$1 \leq N \leq 10^5$, $0 \leq x_i \leq 10^9$.

Output

Print the maximum sum scores you can gain.

Samples

4
1 4 3 2

3

Note

In the sample, scores $3$ will be gained if number $3$ is deleted first and number $4$ is deleted then; scores $2$ will be gained if number $4$ is deleted first and number $3$ is deleted then. So the answer is $3$.

Resources

The 15th UESTC Programming Contest Final