Removing Blocks

Problem Description

There are $n$ piles of blocks; the $i$-th pile is made of $h_i$ blocks stacked up (see the sample).

Now we remove blocks. A block is called an inner block if and only if its up, down, left and right neighbours are all blocks or the ground; otherwise it is a boundary block. In each operation we remove all boundary blocks.

Find after how many operations all blocks disappear.

Input Format

The first line contains an integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $h_i$ ($1 \le h_i \le 10^9$), the number of blocks in each pile.

Output Format

Output the number of operations needed for all blocks to disappear.

Sample Input

6
2 1 4 6 2 2

Sample Output

3

Sample Explanation

Constraints

For all data, $1 \le n \le 10^5$ and $1 \le h_i \le 10^9$.