Problem C
Greedy Landlords

Yellow and Black Heavy Equipment Under Blue Sky. Photo by Omkar Patyane

There is a row of $N$ apartment buildings in a Westwood that have been abandoned after finals week. The greedy landlords want to start demolishing apartments and rebuilding newer ones to make more money. To destroy the old apartments, two bulldozers approach the buildings from either ends of the street. It only takes the bulldozers one hour to destroy each building, so after the first hour, the two buildings on the two ends of the row will be destroyed. The robber takes one hour to get into an apartment building, loot it, and get out, so if the robber started at time $t = 0$ at one of the endmost houses, he’d be able to successfully rob the house before getting demolished by the bulldozers. So even if a bulldozer was right next to an apartment building, the robber would have enough time to loot it and get out.

The bulldozers work their way closer to the center, as they destroy an apartment building on either side of the street (a total of $2$ houses) every hour. When there are an odd number of houses, the last remaining house is destroyed by one of the bulldozers in the last hour. The robber can only realistically move to the adjacent building once it has robbed one, so he cannot decide to jump multiple buildings over at any point in time. Each apartment building has a value associated with it as in the amount that the robber can steal from the building.

What is the maximum amount that the robber can loot from the row of apartment buildings given that he can keep robbing them until all of the buildings have been bulldozed?

Input

The first line of input contains a single integer $N$ such that $3 \le N \le 200\, 000$. The second line of input contains a row of $N$ space-separated integers $p_1, p_2, \dots p_ N$ such that $0 \le p_ i \le 1\, 000\, 000$ where $p_ i$ is the value associated with the $i^\textrm {th}$ house in the row of houses.

Output

Print a single integer that represents the maximum amount of money that the robber can steal from the row of houses before the two bulldozers run over the entire row of $N$ houses.

Sample Explanation

Consider the example with $6$ houses having values $6$, $4$, $1$, $12$, $7$, and $10$. We will use zero based indexing in this example. The maximum that the robber can loot from this row of buildings is $29$. In the first hour, the robber loots the house at index $5$ thus gaining a value of $10$. He hops to the next house, i.e. house at index $4$ before the bulldozers destroy houses at index $0$ and index $5$. He then loots the house at index $4$ and gains $7$, after which the robbers destroy houses at index $1$ and $4$. The robber then hops to the next house at index $3$ which he loots and then gets out just in time before the bulldozers destroy the houses at index $2$ and $3$. In this way, the robber gains a total value of $29$.

6
6 4 1 12 7 10

29

8
1 1 100 100 100 1 1 1

301