Problem Description

You are playing a treasure-hunting game. There are $n$ cells numbered from $1$ to $n$. Each time you dig down by one layer in cell $i$, you gain a value of $p_i$.

You must ensure that for any two adjacent cells, the difference between their digging depths is at most $1$ (note that cells $1$ and $n$ can be dug down by at most one layer). 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.

5
1 3 -4 2 1

8

4
1 1 -2 3

5

5
-1 -3 0 -5 -4

0

Hint

Explanation for Sample 1:

Translated by ChatGPT 5