Ivan has got an array of n non-negative integers a1,a2,...,an. Ivan knows that the array is sorted in the non-decreasing order.
Ivan wrote out integers 2a1,2a2,...,2an on a piece of paper. Now he wonders, what minimum number of integers of form 2b (b≥0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2v-1 for some integer v (v≥0).
Help Ivan, find the required quantity of numbers.
The first line contains integer n (1≤n≤105). The second input line contains n space-separated integers a1,a2,...,an (0≤ai≤2·109). It is guaranteed that a1≤a2≤...≤an.
Print a single integer − the answer to the problem.
4
0 1 1 1
0
1
3
3
In the first sample you do not need to add anything, the sum of numbers already equals 23-1=7.
In the second sample you need to add numbers 20,21,22.