Ivan has got an array of n non-negative integers a₁,a₂,...,a_n. Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers 2^a₁,2^a₂,...,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⁵). The second input line contains n space-separated integers a₁,a₂,...,a_n (0≤a_i≤2·10⁹). It is guaranteed that a₁≤a₂≤...≤a_n.

Print a single integer − the answer to the problem.