계단

면접 대비

시간 제한0.25초메모리 제한256 MB

요약

기둥 높이들이 주어질 때, 왼쪽에서 i번째 기둥의 높이가 i 이상인 가장 긴 연속 구간의 길이를 구한다.

문제

자료의 분포를 아래 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다.

히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역입니다.

계단의 '길이'는 계단에 포함된 히스토그램 열의 수입니다.
계단의 길이가 $L$ 일 때, 왼쪽에서 $i$ 번째 열의 높이는 $i$ 입니다. 즉, 맨 왼쪽 열의 높이는 1, 그다음 열의 높이는 2이고, 맨 오른쪽 열의 높이는 $L$ 입니다.

히스토그램 영역이 계단을 포함하면 되므로, 히스토그램의 높이가 계단의 높이 이상이기만 하면 되고 정확히 같을 필요는 없습니다.

위 히스토그램에서 가장 큰 계단은 아래와 같습니다. 가장 큰 계단이란 길이가 가장 긴 계단을 말합니다. 히스토그램이 입력으로 주어질 때 가장 큰 계단의 길이를 구해 봅시다.

첫 줄에는 히스토그램의 열의 수를 나타내는 정수 $N$ 이 주어집니다.

둘째 줄에는 각 열의 높이를 나타내는 정수 $A_1, A_2, \cdots, A_N$ 이 주어집니다.

히스토그램에서 가장 긴 계단의 길이를 출력합니다.