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.
#!/usr/bin/env python
# -*- coding: UTF-8 -*-

import sys
import itertools

DEBUG = 0

def ReadIn():
    data = [int(x) for x in sys.stdin.read().split()]
    offset = 0
    while offset < len(data):
        n = data[offset]
        offset += 1
        yield data[offset : offset + n]
        offset += n

def Solve(a):
    if DEBUG: print 'a =', a
    idx = 0
    now = 0
    ans = 0
    for key in a:
        while idx < key and now:
            if ~now & 1: ans += 1
            now >>= 1
            idx += 1
        if DEBUG: print idx, now, ans
        now += 1
        ans += key - idx
        idx = key
    while now:
        if ~now & 1: ans += 1
        now >>= 1
        idx += 1

    print ans

if __name__ == '__main__':
    for a in ReadIn():
        Solve(a)
