Eagle

An eagle lives by eating sheep. The place where the sheep live can be represented as a $1 \times N$ rectangle divided into $1 \times 1$ cells. The cells are numbered $1, 2, \dots, N$ from left to right. The number of sheep living in cell $i$ is $A_i$.

The eagle goes out to eat sheep every morning. It starts flying from the left of cell $1$ or the right of cell $N$ and flies to the cell whose sheep it wants to eat. The eagle cannot fly outside the cells. If the sheep it wants to eat are in cell $x$, it flies to cell $x$ and then eats all the sheep in cell $x$. In one day the eagle can eat the sheep of only one cell.

Sheep are very afraid of the eagle, so they run away when they see it flying. A sheep runs away when it sees the eagle flying above its cell. When sheep run away, the number of sheep in that cell becomes $0$. For example, if the eagle starts flying from the left of cell $1$ and arrives at cell $x$, then all the sheep that were in cells $1$ through $x-1$ run away and become $0$. If it starts flying from the right of cell $N$, then all the sheep in cells $x+1$ through $N$ run away.

Also, because this is a dangerous place, every night the number of sheep in every cell decreases by $1$.

How many sheep the eagle can eat depends on which cell's sheep it eats each day and from which side it starts flying.

Given the numbers of sheep, write a program to find the maximum number of sheep the eagle can eat.

The first line gives the number of cells $N$. ($1 \le N \le 1{,}000$)

The second line gives the number of sheep in each cell, $A_1, A_2, \dots, A_N$. ($0 \le A_i \le 100{,}000$)

On the first line, print the maximum number of sheep the eagle can eat.