Alien Invasion

The land of Byteland has $n$ cities lined up along a single road. Reading the road from left to right, the cities are numbered $1$ through $n$, and city $i$ is home to $a_i$ residents.

The aliens always strike at night, hitting at most one city per night. Each strike is instantaneous: every resident of the attacked city is abducted at once and carried off to the aliens' galaxy.

To protect people, the scientists warn the other cities with trained rats. When the aliens attack a city, two rats set off from it in opposite directions along the road, carrying news of the raid. Crossing one segment of the road takes them almost a full day, so news sent from city $j$ reaches city $k$ just before nightfall on the $|k-j|$-th day after the attack. Residents who receive the warning hide in shelters beyond the reach of the aliens' tentacles; the shelters are well stocked, so they stay there until the aliens stop attacking and return to their galaxy.

This scheme cannot always save everyone. The scientists want to know how many residents can be abducted in the worst case, that is, when the aliens attack so as to maximize the number of people taken.

The first line contains the number of cities $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), separated by spaces, giving the number of residents in each city along the road.

Print a single integer: the maximum number of residents that can be abducted in the worst case.