문제 97

양끝에서 공부하기

태그 보기

그리디 알고리즘두 포인터

난이도 $A_1$, $A_2$, $\cdots$, $A_N$인 문제가 일렬로 놓여 있다.

초기 실력이 $X$일 때, 남은 문제의 양끝 중 난이도가 현재 실력 이하인 문제 하나를 풀 수 있다. 문제를 풀면 해당 문제는 제거되고 실력이 $1$ 증가한다.

모든 문제를 풀 수 있는 정수 $X$의 최솟값을 구하여라.

입력

첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄에 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 10^9)$

초기 실력 $X$의 최솟값을 출력한다.

4
4 0 0 0

5
0 4 0 0 0

5
2 1 8 0 3

언어