A9027 | Ivan and Powers of Two

Ivan has got an array of $n$ non-negative integers $a_{1},a_{2},...,a_{n}$ . Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers $2^{a_{1}},2^{a_{2}},...,2^{a_{n}}$ on a piece of paper. Now he wonders, what minimum number of integers of form $2^{b}$ $(b>=0)$ need to be added to the piece of paper so that the sum of all integers written on the paper equalled $2^{v}-1$ for some integer $v$ $(v>=0)$ .

Help Ivan, find the required quantity of numbers.

The first line contains integer $n$ ( $1<=n<=10^{5}$ ). The second input line contains $n$ space-separated integers $a_{1},a_{2},...,a_{n}$ $(0<=a_{i}<=2·10^{9})$ . It is guaranteed that $a_{1}<=a_{2}<=...<=a_{n}$ .

Print a single integer — the answer to the problem.