끝까지 남는 수 2

길이가 $N$인 양의 정수 수열 $A_1,A_2,\ldots,A_N$이 주어진다. 정수가 하나 남을 때까지 다음 연산을 반복한다.

• 현재 남아 있는 정수 하나를 선택하여 제거한다. 제거한 정수의 값을 $x$라 하자.
• 남아 있는 정수 중 값이 $x$ 이하인 모든 정수의 값을 각각 $1$ 증가시킨다.

값을 증가시킬 대상은 해당 연산에서 증가시키기 전의 값으로 판단한다. 같은 값을 가진 정수가 여러 개 있더라도 선택한 정수 하나만 제거한다.

마지막에 남는 정수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

마지막에 남는 정수의 최솟값을 출력한다.

• $1\le N\le200\,000$.
• $1\le A_i\le10^9$ ().