P10736 [SEERC 2020] Archeologists

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.

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 the maximum total value.

Explanation for Sample 1:  Translated by ChatGPT 5