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