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: MEDIUM_HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
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
st = []
tot = 0
idx = 0
for i in range(0, d):
	while idx < b[i]:
		if tot == 0:
			break
		elif 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)


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()


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()


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())
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())
seq = [int(x) for x in input().split()]

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)


import io
import os
import sys
from atexit import register
import random
import math
import itertools
DEBUG = True
STRESSTEST = False
if not DEBUG:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
tokens = []
tokens_next = 0

def nextStr():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = input().split()
		tokens_next = 0
	tokens_next += 1
	if type(tokens[tokens_next - 1]) == str:
		return tokens[tokens_next - 1]
	return tokens[tokens_next - 1].decode()

def nextInt():
	return int(nextStr())

def nextIntArr(n):
	return [nextInt() for i in range(n)]

def print(*argv, end='\n'):
	for arg in argv:
		sys.stdout.write((str(arg) + ' ').encode())
	sys.stdout.write(end.encode())

def genTestCase():
	raise NotImplementedError

def bruteforce(a):
	raise NotImplementedError

def doStressTest():
	while True:
		curTest = genTestCase()
		mySoln = solve(curTest)
		bruteforceSoln = bruteforce(curTest)
		if mySoln != bruteforceSoln:
			print('### Found case ###')
			print(curTest)
			print(f'{mySoln} should have been: {bruteforceSoln}')
			return

def solve(a):
	s = set()
	for c in a:
		if c in s:
			t = c
			while t in s:
				s.remove(t)
				t += 1
			s.add(t)
		else:
			s.add(c)
	return max(s) - len(s) + 1
if not DEBUG and STRESSTEST:
	raise Exception('Wrong flags!')
if STRESSTEST:
	doStressTest()
else:
	a = nextIntArr(nextInt())
	res = solve(a)
	print(res)
sys.stdout.flush()


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 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]
	for i in range(len(bineq)):
		if i == 0:
			if bineq[i] == '0':
				del d[x + i]
			else:
				d[x + i] = 1
		elif 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))


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


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())
ar = list(map(int, input().split()))
b = set()
maxx = 0
for i in ar:
	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 = 0
c = 0
d = 0
for i in range(1, n):
	if a[i] != a[i - 1]:
		c += 1 - (i - b + d) % 2
		d = (i - b + d) // 2
		j = a[i - 1] + 1
		while j < a[i] and d > 0:
			c += 1 - d % 2
			d //= 2
			j += 1
		c += a[i] - j
		b = i
c += 1 - (n - b + d) % 2
d = (n - b + d) // 2
j = a[-1] + 1
while d > 0:
	c += 1 - d % 2
	d //= 2
	j += 1
print(c + a[0])


from sys import stdin

def read():
	return 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)


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)


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()))
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())
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)