305_C. Ivan and Powers of Two_10271
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.

Input

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.

Output

Print a single integer — the answer to the problem.

Examples

Input

4
0 1 1 1


Output

0


Input

1
3


Output

3

Note

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.
n = int(input())
a = list(map(int, input().split()))
s = set()
for i in a:
    j = i
    while j in s:
        s.remove(j)
        j += 1
    s.add(j)
print(max(s)-len(s)+1)

1
3
 4
0 1 1 1
 1
2000000000
 26
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2
 1
0
 1
1
 1
1646661570
 1
2
 1
4
 1
110164340
 1
8
 1
7
 1
127913041
 1
12
 1
130811826
 1
9
 1
80666671
 1
130474002
 1
162907766
 1
161567958
 1
204470614
 1
399291558
 1
219330401
 1
13834924
 1
13149123
 1
11668780
 1
1549242
 1
1910848
 1
625466
 1
569444
 1
441924
 1
693187
 1
11439
 1
15843
 1
13601
 1
1863
 1
900
 1
1797
 1
188
 1
47
 1
92
 1
50
 1
69
 1
73
 1
51
 1
53
 1
65
 1
45
 1
5
 1
6
 1
10
 1
18
 1
16
 1
22
 1
17
 1
13
 1
37654189
 1
14
 1
233315811
 1
20
 1
177669829
 1
11
 1
32494636
 1
110620189
 1
208078461
 1
81836186
 1
84901711
 1
461153241
 1
376990154
 1
7737018
 1
622792
 1
22498425
 1
1947988
 1
2080825

3
 0
 2000000000
 5
 0
 1
 1646661570
 2
 4
 110164340
 8
 7
 127913041
 12
 130811826
 9
 80666671
 130474002
 162907766
 161567958
 204470614
 399291558
 219330401
 13834924
 13149123
 11668780
 1549242
 1910848
 625466
 569444
 441924
 693187
 11439
 15843
 13601
 1863
 900
 1797
 188
 47
 92
 50
 69
 73
 51
 53
 65
 45
 5
 6
 10
 18
 16
 22
 17
 13
 37654189
 14
 233315811
 20
 177669829
 11
 32494636
 110620189
 208078461
 81836186
 84901711
 461153241
 376990154
 7737018
 622792
 22498425
 1947988
 2080825
