Problem Description

You are playing a treasure-hunting game with a total of $n$ grids, numbered from $1$ to $n$. Each time you dig one layer deeper in the $i$-th grid, you gain a value of $p_i$. You must ensure that the difference in digging depth between any two adjacent grids does not exceed $1$ (note that the $1$st and $n$-th grids can be dug at most one layer deep). Please maximize the total value.

Input Format

The first line contains an integer $n\ (1 \leq n \leq 2.5 \times 10^5)$.

The next line contains $n$ integers $p_i\ (-10^6 \leq p_i \leq 10^6)$.

Output Format

Output the maximum total value.

Sample Input and Output

Sample Input #1

5
1 3 -4 2 1

Sample Output #1

8

Sample Input #2

4
1 1 -2 3

Sample Output #2

5

Sample Input #3

5
-1 -3 0 -5 -4

Sample Output #3

0

Notes

Explanation for Sample #1:

见题面 Input 部分

见题面 Output 部分