J. Strange Sum
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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

Output a single integer denoting the answer.

Examples
Input
4
1 4 3 2
Output
7
Input
3
-10 -10 -10
Output
0