Isosceles Cube Triangle

Interview

Time limit1sMemory limit512 MB

Summary

Given column heights, find the largest h such that some 2h-1 consecutive columns can all be reduced to the shape 1,2,...,h,...,2,1.

Level: Medium5 of 10
Topics: Array, Brute force, Prefix sum
Solved: No attempts yet

Problem

The brothers Sergio and Luiz built a wall out of small wooden cubes. They never finished it, so the columns have different heights.

Now they want to play a different game: take cubes away until a single complete isosceles triangle is left. A cube can only be taken from the top of a column, and a cube that has been taken away cannot be put back on another column.

An isosceles triangle of height $h$ occupies $2h-1$ consecutive columns whose heights, from left to right, are exactly $1, 2, \dots, h-1, h, h-1, \dots, 2, 1$ . The picture below shows the triangles of heights 1, 2, 3, 4 and 5.

Every column that is not part of the triangle has to be emptied completely. Given the heights of the columns of the wall in order, write a program that finds the greatest height a remaining triangle can have. In the wall of the first picture, which has 30 columns, the tallest possible triangle has height 7.

Input

The first line contains an integer $N$ , the number of columns of the wall. The second line contains $N$ integers $A_i$ , the heights of the columns from left to right.

Constraints

$1 \le N \le 50\,000$
$1 \le A_i \le N$

Output

Print a single line with one integer $H$ , the greatest height a remaining triangle can have.

Examples2

Example 1
Input
```
16
5 6 5 8 9 10 5 8 9 5 7 9 9 9 6 3
```
Expected output
```
6
```
Example 2
Input
```
8
5 1 1 1 1 1 1 3
```
Expected output
```
1
```