Problem Statement

There are $N$ cells arranged in a horizontal row, numbered $1, 2, \dots, N$ from left to right.

Each cell has $1$ fruit tree planted in it, and it is known that the fruit of the tree in cell $i$ ripens at time $A_i$. Once a fruit has ripened, it does not disappear until it is harvested.

Tanuki-kun can start from any cell at time $0$. Since Tanuki-kun is not good at sudden movements, in each unit of time he can only either move to an adjacent cell or stay in his current cell. At any moment, he can harvest the ripened fruit of the tree in the cell he is in. Since Tanuki-kun is a harvesting professional, the time needed for harvesting can be ignored.

Tanuki-kun is hungry, so he wants to harvest the fruit of the trees in all cells as early as possible. Find the earliest time at which he can finish harvesting the fruit of the trees in all cells.

Input

$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$

The $1$st line gives the number of cells $N(1 \le N \le 2\ 000)$.

The $2$nd line gives $N$ values separated by single spaces. The $i(1 \le i \le N)$-th of these values means that the fruit of the tree in cell $i$ ripens at time $A_i(0 \le A_i \le 10^9)$.

Output

Output, on 1 line, the earliest time at which Tanuki-kun can finish harvesting the fruit of the trees in all cells.

Print a newline at the end.

Sample

3
0 1 1

2

3
5 1 4

6

3
1333 1000000000 1333

1000000000