410697: GYM104077 J Strange Sum

Given a sequence $$$a_1, a_2, \ldots, a_n$$$.

You are going to select zero or more elements of $$$a$$$ so that: if you select $$$a_i$$$, then in any interval of length $$$i$$$ (formally, in $$$a[j, j + i - 1]$$$ for any $$$1 \le j \le n - i + 1$$$) you can select at most $$$2$$$ elements.

Calculate the maximal sum of the elements you select.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

Output a single integer denoting the answer.

4
1 4 3 2

7

3
-10 -10 -10

0