Problem Description
After doing setsquare, Guan has acquired a new brilliant plan :D
On a street with N grids, where each grid has a height limit Hi, Guan wishes to erect a half-pyramid hotel
The half-pyramid hotel must face right (i.e. from left to right the height of the hotel will be strictly decreasing)
The heights of the buildings constituting the hotel must be a sequence of consecutive numbers, with the smallest consecutive number being 1
I.e. from left to right, 3,2,1 or 4,3,2,1 or 6,5,4,3,2,1
Guan wants to find out the maximum height of the largest possible pyramid hotel he can erect. Help him
Input
The first line contains the number of city grids, N
The next N lines contain the height limit of each grid, Hi, from left to right
Constraints
1<=Hi<=1,000,000
1<=N<=1,000,000
Output
A single number, the maximum height of the largest possible pyramid hotel Guan can erect
Subtasks
Subtask 1 (3%) Hi=N-i (i starts from 1 and ends with N)
Subtask 2 (23%) N<=1,000
Subtask 3 (74%) N<=1,000,000
Warning
Please use scanf/printf or put the line ios_base::sync_with_stdio(false) if using cin/cout (And avoid using scanf/printf), or you will TLE
Sample Testcase 1
Input
6
6 5 4 3 2 1
Output
6
Explanation
Guan builds a hotel from the leftmost grid of heights 6,5,4,3,2,1
Sample Testcase 2
Input
6
1 2 3 4 5 6
Output
3
Explanation
Guan builds a hotel of 3,2,1 on the tiles with a height limit of 3,4,5 respectively