P14481 Destined Orbit of the Stars

[Hope Is the Thing With Feathers](https://music.163.com/#/song?id=2155423468&uct2=U2FsdGVkX18f8x2vk0UIP7x3oSx/Ty1Xey38hrzDsOU=).

[wwwwwza](https://www.luogu.com.cn/user/559526) 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$.

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

Output one line representing the answer.

### 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. | Test Data | $n\le$ | | :-----------: | :-----------: | |$1$|$10$| |$2\sim 3$|$200$| |$4\sim 5$|$2000$| |$6\sim 9$|$10^5$| |$10$|$10^6$| 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.**