Isosceles
By Maratona de Programação da SBC 2016 
Brazil
By Maratona de Programação da SBC 2016 Brazil
The brothers Sergio and Luiz were playing with wooden cubes and wanted to build a wall, which ended up being incomplete, with the columns having different heights, as in this figure.
They decided now that the game would remove cubes, always from top to bottom in columns so that the end was left only an isosceles triangle cubes. They can only take small cubes of the wall, without replacing in another column, and the triangles have to be complete. The figure below illustrates the top five isosceles triangles, cubes, the kind they want, with heights 1, 2, 3, 4 and 5 respectively.
Given the sequence of heights of the wall columns, your program should help Sergio Luiz and figure out what is the maximum height that the triangle could be the end. In the first figure wall 30 columns of cubes, the highest triangle can have a height equal to seven.
The first line of input contains an integer N, 1 ≤ N ≤ 50000, representing the number of the wall columns. The second line contains N integers Ai, 1 ≤ Ai ≤ N, for 1 ≤ i ≤ N, indicating the heights of each column.
Your program should produce a single line with an integer M, representing the maximum height that a triangle could be the end.
| Input Samples | Output Samples |
|
16 |
6 |
|
8 |
1 |