31235번 - 올라올라

문제

길이가 $N$인 수열 $A$가 주어질 때, $N$ 이하의 양의 정수 $k$에 대하여 길이가 $N-k+1$인 수열 $B$를 다음과 같이 정의하자.

$$B_{i}=\max_{i \le j \le i+k-1}A_j$$

수열 $B$가 감소하지 않도록 하는 $k$의 최솟값을 구해보자.

예를 들어 $A=\{3,1,4,2,5\}$이고 $k=2$라면, $B=\{3,4,4,5\}$이므로 감소하지 않지만, $k=1$이라면 $B=\{3,1,4,2,5\}$이므로 감소하는 부분이 존재한다. 이 경우 $k$의 최솟값은 2ドル$이다.

입력

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 10^6)$

둘째 줄에는 $A_1, \dots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

입력으로 주어지는 모든 수는 정수이다.

출력

문제의 조건을 만족하는 $N$ 이하의 양의 정수 $k$ 중 최솟값을 출력하라.

제한

힌트