Staircase

Interview

Time limit0.25sMemory limit256 MB

Summary

Given column heights, find the longest contiguous run where the i-th column from the left has height at least i.

Level: Medium4 of 10
Topics: Array, Greedy, Implementation, Two pointers
Solved: No attempts yet

Problem

A graph that shows the distribution of data as in the figure below is called a histogram.

You want to find the largest staircase in the histogram region. A staircase is a region that satisfies the following conditions.

The 'length' of a staircase is the number of histogram columns it contains.
When the length of a staircase is $L$ , the height of the $i$ -th column from the left is $i$ . That is, the leftmost column has height 1, the next column has height 2, and the rightmost column has height $L$ .

The histogram region only needs to contain the staircase, so the histogram's height only needs to be at least the staircase's height; it does not need to be exactly equal.

In the histogram above, the largest staircase is shown below. The largest staircase means the staircase with the greatest length. Given a histogram as input, find the length of the largest staircase.

Input

The first line contains an integer $N$ , the number of columns in the histogram.

The second line contains integers $A_1, A_2, \cdots, A_N$ , the heights of the columns.

Output

Print the length of the longest staircase in the histogram.

Constraints

$1 \le N \le 10^5$
$1 \le A_i \le 10^9$

Examples2

Example 1
Input
```
5
1 3 2 3 1
```
Expected output
```
3
```
Example 2
Input
```
13
3 1 4 1 5 9 2 6 5 3 5 8 9
```
Expected output
```
6
```