最後に残る数 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$ ().