The Byteotian Institute of Exobiology has just established the Department for Warning against Dangers from Space. The scientists employed there are tasked with doing everything possible to protect the citizens of Byteotia from the consequences of an alien invasion, which is bound to happen.
There are $n$ cities in Byteotia, located along the Byteoroad. We will number the cities consecutively from 1 to $n$. In city $i$, there are $a_i$ citizens.
As is well known, aliens always attack at night, targeting at most one city. Unfortunately, their attack is instantaneous—all residents of the attacked city are immediately abducted and transported to the aliens' galaxy.
Scientists at the department are working on a way to protect the residents. Since aliens are not interested in Byteotian rodents, the scientists decided to use trained rats to warn the remaining cities in Byteotia. When the aliens attack a city, two rats will set off from that city in opposite directions along the Byteoroad, carrying news of the attack. Running one segment of the Byteoroad takes them almost an entire day; therefore, a message sent from city $j$ will reach city $k$ just before dusk on the $|k - j|$-th day after the attack. Alerted residents hide in shelters, where the aliens' tentacles cannot reach them. Since Byteotian shelters are well-stocked, the warned residents will remain in them until the aliens cease their attacks and return to their galaxy.
As can be seen, the described system will not necessarily save all citizens of Byteotia. The scientists are wondering how many residents will be abducted in the worst-case scenario.
Input
The first line of input contains an integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of cities in Byteotia. The second line contains a sequence of integers $a_1, \ldots, a_n$ ($0 \le a_i \le 10^9$). These represent the number of residents in the consecutive cities located along the Byteoroad.
Output
The only line of output should contain an integer representing the maximum possible number of abducted residents.
Examples
Input 1
6 5 9 1 3 7 2
Output 1
16