Ivan has got an array of n non-negative integers a_1, a_2, ..., a_{n}. Ivan knows that the array is sorted in the non-decreasing order. 

Ivan wrote out integers 2^{a}_1, 2^{a}_2, ..., 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.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second input line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 2·10^9). It is guaranteed that a_1 ≤ a_2 ≤ ... ≤ a_{n}.


-----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 2^3 - 1 = 7.

In the second sample you need to add numbers 2^0, 2^1, 2^2.

Difficulty: interview

Starter code:

Solutions:
input()
a = list(map(int, input().split()))
b = []
i = j = 0
while i < len(a):
  while j < len(a) and a[j] == a[i]:
    j += 1
  if (j - i) % 2 == 1:
    b += [a[i]]
  i = j - (j - i) // 2
  for k in range(i, j):
    a[k] += 1
print(b[-1] - len(b) + 1)

n = int(input())
I = list(map(int, input().split()))
a = [];
for val in I:
    a.append(val);
la = len(a);
b = []; c = []; d = -1;
for i in range (0, la):
    if i == 0 or a[i] != a[i-1]:
        b.append(a[i]);
        c.append(1);
        d = d + 1;
    else:
        c[d] = c[d] + 1;
d = d + 1;
tot = 0; idx = 0;
for i in range(0, d):
    while idx < b[i]:
        if tot < 2:
            break;
        else:
            tot = int(tot / 2);
            idx = idx + 1;
    if idx < b[i]:
        idx = b[i];
        tot = c[i];
    else:
        tot = tot + c[i];
while tot >= 2:
    tot = int(tot / 2);
    idx = idx + 1;
idx = idx + 1;
res = idx;
#print (idx)
st = []; tot = 0; idx = 0;
for i in range (0, d):
    while idx < b[i]:
        if tot == 0:
            break;
        else:
            if tot == 1:
                st.append(idx);
                tot = 0; idx = idx + 1;
            else:
                if tot % 2 == 1:
                    st.append(idx);
                tot = int(tot / 2);
                idx = idx + 1;
    if idx < b[i]:
        idx = b[i]; tot = c[i];
        if tot % 2 == 1:
            st.append(idx);
        tot = int(tot / 2);
        idx = idx + 1;
    else:
        idx = b[i]; tot = tot + c[i];
        if tot % 2 == 1:
            st.append(idx);
        tot = int(tot / 2);
        idx = idx + 1;
while tot > 0:
    if tot % 2 == 1:
        st.append(idx);
    tot = int(tot / 2);
    idx = idx + 1;
lst = len(st);
print(res- lst)









input()
now = 0
alc = 0
ans = 0
for v in map(int, input().split()):
    if not alc or now == v:
        if not alc:
            ans += v
        now = v
        alc += 1
    else:
        while alc and now != v:
            ans += not (alc & 1)
            alc >>= 1
            now += 1
        ans += v - now
        alc += 1
        now = v
else:
    while alc:
        ans += not (alc & 1)
        alc >>= 1
print(ans)


input()
now = alc = ans = 0
for v in map(int, input().split()):
    while alc and now != v:
        ans += not (alc & 1)
        alc >>= 1
        now += 1
    ans += v - now
    alc += 1
    now = v
else:
    while alc:
        ans += not (alc & 1)
        alc >>= 1
print(ans)


n=int(input())
a=list(map(int,input().split()))
c=1
v=0
p=a[0]

for i in range(1,n):
    if a[i]==a[i-1]:
        c+=1
    else:
        while c>0 and p<a[i]:
            v+=(c%2)
            c//=2
            p+=1
        c+=1
        p=a[i]

while c>1:
    v+=(c%2)
    c//=2
    p+=1
    
print(p-v)
    
        


from sys import stdin, stdout

n = int(stdin.readline())
t = list(map(int, stdin.readline().split()))

y = s = t[0]
x = i = 1
while True:
    while i < n and t[i] == y:
        i += 1
        x += 1

    s += (x + 1) & 1
    x //= 2
    y += 1

    if x: continue
    if i == n: break
    
    s += t[i] - y
    x, y = 1, t[i]
    i += 1        

print(s)

from sys import stdin, stdout
n = int(stdin.readline())
y = s = x = 0
for i in map(int, stdin.readline().split()):
    if i == y: x += 1
    else:
        while x and i > y:
            if not x & 1: s += 1
            x >>= 1
            y += 1
        if i > y:
            s += i - y
            x, y = 1, i
        else: x += 1
while x:
    if not x & 1: s += 1
    x >>= 1
print(s)

n=int(input())
a=list(map(int,input().split()))
st=set()
for e in a :
    while(e in st):
        st.remove(e)
        e+=1
    st.add(e)
print(max(st)-len(st)+1)


n=int(input())
st=set()
for e in map(int,input().split()):
    while(e in st):
        st.remove(e)
        e+=1
    st.add(e)
print(max(st)-len(st)+1)

from sys import stdin

N = int(stdin.readline())

num = set()

for b in map(int, stdin.readline().split()):
    while b in num:
        num.remove(b)
        b += 1

    num.add(b)

print(max(num) - len(num) + 1)


n=int(input())
st=set()
for e in map(int,input().split()):
    while(e in st):
        st.remove(e)
        e+=1
    st.add(e)
print(max(st)-len(st)+1)

from sys import stdin

def read(): return list(map(int, stdin.readline().split()))

read()
s = set()
for x in read():
  while x in s:
    s.remove(x)
    x += 1
  s.add(x)

print( max(s) - len(s) + 1 )


from sys import stdin, stdout

inputIdx = 0;
input = stdin.read().strip().split();

def nextToken():
  nonlocal inputIdx, input;
  token = input[inputIdx];
  inputIdx += 1;
  return token;

def main():
  nonlocal inputIdx, input;
  while inputIdx < len(input):
    n = int( nextToken() );
    arr = [ int( nextToken() ) for i in range(n) ];
    diff = 0;
    cur = -1; cnt = 0;
    i = 0;
    ans = max(arr);
    while i < n or cur != -1:
      ans = max( ans, cur );
      if ( i < n and cur != -1 and arr[i] == cur ) or ( cur == -1 ):
        j = i;
        while j < n and arr[i] == arr[j]:
          j += 1;
        cnt += j-i;
        cur = arr[i];
        i = j;
      if (cnt&1) == 1:
        diff += 1;
      cur += 1;
      cnt //= 2;
      if cnt == 0:
        cur = -1;
    ans -= diff-1;
    print(( int(ans) ));

main();


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

s=set()

mx=0
cnt=0

for i in a:
    k=int(i)
    while k in s :
          s.remove(int(k))
          cnt=cnt-1
          k=k+1
    s.add(k)
    if mx<k: mx=k
    cnt=cnt+1

print(mx-cnt+1)





n=int(input())

st=set()

for e in map(int,input().split()):

    while(e in st):

        st.remove(e)

        e+=1

    st.add(e)

print(max(st)-len(st)+1)



# Made By Mostafa_Khaled


n=int(input())
st=set()
for e in map(int,input().split()):
   # print(st,'beg')
    while(e in st):
        st.remove(e)
        e+=1
    st.add(e)
    #print(st)
print(max(st)-len(st)+1)
#print(max(st))


n=int(input())
a=list(map(int,input().split()))
b=set()
for i in a:
	while i in b:
		b.remove(i)
		i+=1
	b.add(i)
print(max(b)-len(b)+1)

n=int(input())
a=list(map(int,input().split()))
b=set()
for i in a:
	while i in b:
		b.remove(i)
		i+=1
	b.add(i)
print(max(b)-len(b)+1)

n = int(input())
seq = [int(x) for x in input().split()]

# print(seq)

def inseri(s, n):
	if n in s:
		s.remove(n)
		inseri(s, n+1)
	else:
		s.add(n)


s = set()
for i in seq:
	inseri(s, i)

m = max(s)
print(m-len(s)+1)
# print(s)


# array de indices em ordem crescente
# quantos 2**b precisa para 2**v-1 (soma de sequencia)

import math

def main():
    n = int(input())
    a = input().split()
    a = [int(x) for x in a]
    
    p = 0
    carry = 0
    ok = 0
    while p<n:
        count = carry
        atual = a[p]
        while p<n and a[p] == atual:
            count += 1
            p += 1 
        if count%2 == 1:
            ok += 1
        carry = count//2 
        if p<n:       
            proximo = a[p]
        else:
            proximo = atual-1    
        while carry!= 0 and proximo!= atual+1:
            if carry%2 == 1:
                ok += 1
            carry = carry//2         
            atual += 1
    print(atual-ok+1)    

main()

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

def ins(_set, n):
    if n in _set:
        _set.remove(n)
        ins(_set, n+1)
    else:
        _set.add(n)

ss = set()

for i in s:
    ins(ss, i)

m = max(ss)

print(m - len(ss) + 1)


n = int(input())
seq = [int(x) for x in input().split()]

# print(seq)

def inseri(s, n):
	if n in s:
		s.remove(n)
		inseri(s, n+1)
	else:
		s.add(n)


s = set()
for i in seq:
	inseri(s, i)

m = max(s)
print(m-len(s)+1)

m, s, n = 0, set(), int(input())
for a in map(int, input().split()):
    while a in s:
        s.remove(a)
        a += 1
    s.add(a)
    m = max(m, a)
print(m - len(s) + 1)

n=int(input())
a=list(map(int,input().split()))
b=set()
for i in a:
 while i in b:
  b.remove(i)
  i+=1
 b.add(i)
print(max(b)-len(b)+1)

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)