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.
from heapq import heapify, heappush, heappop

n = int(input())
a = list(map(int, input().split()))

q = []; cnt = 1; d = {}

for i in range(1, n):
    if a[i] == a[i-1]:
        cnt += 1
    else:
        q.append(a[i-1])
        d[a[i-1]] = cnt
        cnt = 1
        
q.append(a[-1])
d[a[-1]] = cnt

heapify(q); maxpow = 0

while len(q) != 0:
    x = heappop(q)
    maxpow = max(maxpow, x)
    
    bineq = bin(d[x])[2:][::-1]
    #print(x, d[x], bineq)
    for i in range(len(bineq)):
        
        if i == 0:

            if bineq[i] == '0':
                del d[x+i]
            else:
                d[x+i] = 1

        else:
            
            if bineq[i] == '1':

                if x+i in d:
                    d[x+i] += 1
                else:
                    d[x+i] = 1
                    heappush(q, x+i)
print(maxpow + 1 - len(d))