양끝에서 공부하기

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

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

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

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

두 번째 줄에 $A_1$, , , 이 공백으로 구분되어 주어진다.

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