Description

wwwwwza is a data structure expert, and today she found a data structure problem.

You have a sequence $v$ of length $n$ indexed starting from $1$, consisting of non-negative integers, and a variable $S$. Initially, $S=0$. You can perform the following operation multiple times:

• Choose three adjacent numbers $a,b,c$ in $v$, then take the minimum of the numbers to the left of $a$ and to the right of $c$ (if they exist) with $\min(a,b,c)$. Then remove these three numbers. This operation adds $b$ to $S$.

Your task is to maximize $S$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th integer is $v_i$.

Output Format

Output one line representing the answer.

10
2 4 0 7 5 7 6 9 6 8

19

9
9 9 8 2 4 4 3 5 3

18

Hint

Sample Explanation 1

Initially, the sequence is $[2,4,0,7,5,7,6,9,6,8]$.

Perform these operations:

1. Choose to remove the three numbers starting from the 7th position $[6,9,6]$. Now the $v$ array becomes $[2,4,0,7,5,7,8]$. However, the 6th and 7th positions need to take the minimum with $\min(6,9,6)=6$. Now the $v$ array becomes $[2,4,0,7,5,6,6]$.

2. Choose to remove the three numbers starting from the 5th position $[5,6,6]$. Now the $v$ array becomes $[2,4,0,7]$. However, the 4th and 5th positions (non-existent) need to take the minimum with $\min(5,6,6)=5$. Now the $v$ array becomes $[2,4,0,5]$.

3. Choose to remove the three numbers starting from the 1st position $[2,4,0]$. Now the $v$ array becomes $[5]$. However, the 0th position (non-existent) and the 1st position need to take the minimum with $\min(2,4,0)=0$. Now the $v$ array becomes $[0]$.

$S=9+6+4=19$, and it can be proven that you cannot obtain a scheme where $S>19$.

Note that you don't need to empty the $v$ array.

Data Range

The test points are equally weighted with 10 points each.

For all data, $1\le n \le 10^6,0\le v_i\le 10^9$.

Please note the constant factor differences between different algorithms. The time and space limits for this problem are twice that of the standard solution.

Please note the special time limit for this problem.