F. Keys Burns Down the House
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One night, Keys accidentally left the stove on when he went to bed! He woke up at 3:00 AM to find his house on fire. As Keys tries to escape, he sees his collection of N manga books on a shelf ($$$1 \lt = N \lt = 10^5$$$). Each manga book has a value to Keys of $$$a_i$$$, and Keys wants to save the most value possible. Every second, he can choose an index and take that manga, leaving behind an empty space. However, after every second, the Fire burns the left and right ends (index $$$1$$$ and $$$N$$$) of the bookshelf, burning either the manga there or nothing if Keys already took that manga. In the next second Keys can save another manga, after which the fire will burn the next ends (index $$$2$$$ and $$$N-1$$$). This will happen until the entire bookshelf if burned up. What is the maximum value of manga that Keys can save?

Input

The first line contains an integer $$$N$$$ ($$$1 \lt = N \lt = 10^5$$$), the length of the bookshelf.

The second line contains $$$N$$$ integers $$$a_1,a_2,…,a_n$$$ ($$$1 \le a_i \le 10^5$$$), the value of each manga book at index $$$i$$$.

Output

Print out $$$1$$$ integer, the maximum value of manga that Keys can save.

Examples
Input
6
1 2 1000 4 5 100
Output
1105
Input
4
1 1000 1000 1
Output
2000
Input
4
1000 1 1 100
Output
1001