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 \ge 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 \ge 0).

Help Ivan, find the required quantity of numbers.

The first line contains integer n (1 \le n \le 105). The second input line contains n space-separated integers a1,a2,...,an (0 \le ai \le 2 \cdot 109). It is guaranteed that a1 \le a2 \le ... \le an.

Print a single integer - the answer to the problem.

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.