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.
/**
 * Created with IntelliJ IDEA.
 * User: Venky
 */
import java.io.*;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class Main {

    static void solve() throws IOException {
        int n = nextInt();
        int[] arr = new int[n];
        ConcurrentHashMap<Integer, Integer> my = new ConcurrentHashMap<Integer, Integer>();
        for(int i=0;i<n;i++)
            arr[i] = nextInt();
        Arrays.sort(arr);
        int c = 0;
        for(int i=0;i<arr.length-1;i++)
        {
            if(arr[i] == arr[i+1])
                c++;
            else
            {
                c++;
                my.put(arr[i], c);
                c = 0;
            }
        }
        if(arr.length > 1)
        {
            if(arr[arr.length-1] == arr[arr.length-2])
            {
                c++;
                my.put(arr[arr.length-1], c);
            }
            else
            {
                my.put(arr[arr.length-1], 1);
            }
        }
        else
        {
            my.put(arr[0], 1);
        }

        Iterator it = my.keySet().iterator();
        while(it.hasNext())
        {
            int key = (Integer)it.next();
            int copyKey = key;
            int count = my.get(key);
            int copyCount = count;
            while( count > 1 )
            {
                if(count % 2 == 1)
                {
                    if(my.containsKey(key))
                    {
                        my.put(key, my.get(key) + 1);
                    }
                    else my.put(key, 1);
                }
                count /= 2;
                key ++;
            }
            if(my.containsKey(key))
            {
                my.put(key, my.get(key) + 1);
            }
            else my.put(key, 1);
            if(my.get(copyKey) == copyCount)
                it.remove();
            else my.put(copyKey, my.get(copyKey) - copyCount);
        }
        it = my.keySet().iterator();
        int maxVal = Integer.MIN_VALUE;
        while (it.hasNext())
        {
            int key = (Integer)it.next();
            if(key > maxVal)
                maxVal = key;
        }
        out.println(maxVal - my.size() + 1);
    }

    static BufferedReader br;
    static StringTokenizer st;
    static PrintWriter out;

    public static void main(String[] args) throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(output);
        solve();
        out.close();
    }

    static long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    static String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = br.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
}
