직사각형이 아니라 정사각형

히스토그램은 공통 밑변을 가지는 $N$개의 인접한 직사각형을 나란히 붙여 만든 다각형이다. 각 직사각형을 막대라고 부른다. 왼쪽에서 $i$번째 막대의 너비는 1이고 높이는 $H\_i$이다.

주어진 히스토그램에 완전히 포함되면서 한 변이 밑변과 평행한 가장 큰 직사각형의 넓이를 구하려고 한다.

그림 1. 예제의 히스토그램. 오른쪽에는 가장 큰 직사각형이 표시되어 있다.

사실은 직사각형이 아니라 가장 큰 정사각형을 구해야 한다. 정사각형의 넓이는 한 변의 길이로 정해지므로, 넓이 대신 한 변의 길이를 출력한다.

그림 2. 예제의 히스토그램. 오른쪽에는 가장 큰 정사각형이 표시되어 있다.

첫째 줄에 정수 $N$이 주어진다. $1 \le N \le 300\,000$.

둘째 줄에 $N$개의 정수 $H\_1, H\_2, \cdots, H\_N$이 공백으로 구분되어 주어진다. $H\_i$ $(1 \le H\_i \le 10^9)$는 $i$번째 막대의 높이이다.

히스토그램에 완전히 포함되면서 한 변이 밑변과 평행한 가장 큰 정사각형의 한 변의 길이를 출력한다.