The Last Remaining Number 2

You are given a sequence of $N$ positive integers $A_1,A_2,\ldots,A_N$. Repeat the following operation until exactly one integer remains.

• Choose and remove one of the remaining integers. Let $x$ be its value.
• Increase every remaining integer whose value is at most $x$ by $1$.

Whether an integer is increased is determined by its value before the increases in that operation. If several integers have the same value, only the chosen occurrence is removed.

Find the minimum possible value of the last remaining integer.

The input is given in the following format:

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

Print the minimum possible value of the last remaining integer.

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