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.
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.text.*;

public class cf305c {

    static BufferedReader br;
    static Scanner sc;
    static PrintWriter out;

    public static void initA() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new FileReader("input.txt"));
            sc = new Scanner(System.in);
            //out = new PrintWriter("output.txt");
            out = new PrintWriter(System.out);
        } catch (Exception e) {
        }
    }

    static boolean next_permutation(Integer[] p) {
        for (int a = p.length - 2; a >= 0; --a) {
            if (p[a] < p[a + 1]) {
                for (int b = p.length - 1;; --b) {
                    if (p[b] > p[a]) {
                        int t = p[a];
                        p[a] = p[b];
                        p[b] = t;
                        for (++a, b = p.length - 1; a < b; ++a, --b) {
                            t = p[a];
                            p[a] = p[b];
                            p[b] = t;
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void initB() {
        try {

            br = new BufferedReader(new FileReader("input.txt"));
            sc = new Scanner(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");

        } catch (Exception e) {
        }
    }

    public static String getString() {
        try {
            return br.readLine();
        } catch (Exception e) {
        }
        return "";
    }

    public static Integer getInt() {
        try {
            return Integer.parseInt(br.readLine());
        } catch (Exception e) {
        }
        return 0;
    }

    public static Integer[] getIntArr() {
        try {
            StringTokenizer temp = new StringTokenizer(br.readLine());
            int n = temp.countTokens();
            Integer temp2[] = new Integer[n];
            for (int i = 0; i < n; i++) {
                temp2[i] = Integer.parseInt(temp.nextToken());
            }
            return temp2;
        } catch (Exception e) {
        }
        return null;
    }

    public static Long[] getLongArr() {
        try {
            StringTokenizer temp = new StringTokenizer(br.readLine());
            int n = temp.countTokens();
            Long temp2[] = new Long[n];
            for (int i = 0; i < n; i++) {
                temp2[i] = Long.parseLong(temp.nextToken());
            }
            return temp2;
        } catch (Exception e) {
        }
        return null;
    }

    public static String[] getStringArr() {
        try {
            StringTokenizer temp = new StringTokenizer(br.readLine());
            int n = temp.countTokens();
            String temp2[] = new String[n];
            for (int i = 0; i < n; i++) {
                temp2[i] = (temp.nextToken());
            }
            return temp2;
        } catch (Exception e) {
        }
        return null;
    }

    public static int getMax(Integer[] ar) {
        int t = ar[0];
        for (int i = 0; i < ar.length; i++) {
            if (ar[i] > t) {
                t = ar[i];
            }
        }
        return t;
    }

    public static void print(Object a) {
        out.println(a);
    }

    public static void print(String s, Object... a) {
        out.printf(s, a);
    }

    public static int nextInt() {
        return sc.nextInt();
    }

    public static double nextDouble() {
        return sc.nextDouble();
    }

    public static void main(String[] ar) {
        initA();
        solve3();
        out.flush();
    }

    private static class trie {

        long val;
        trie left, right, parent;

        trie(long v) {
            val = v;
        }
    }
    static trie root, besar;
    static int size = 0;

    static void join(trie a, trie b) {

        ArrayList<trie> cabang = new ArrayList<trie>();
        cabang.add(b);
        for (int i = 0; i < cabang.size(); i++) {
            long val = cabang.get(i).val;
            trie temp = new trie(val);

            trie c = a;
            while (true) {
                if (val < c.val) {
                    if (c.left != null) {
                        c = c.left;
                    } else {
                        temp.parent = c;
                        c.left = temp;

                        break;
                    }
                }
                if (val > c.val) {
                    if (c.right != null) {
                        c = c.right;
                    } else {
                        temp.parent = c;
                        c.right = temp;
                        if (besar.val < val) {
                            besar = temp;
                        }
                        break;
                    }
                }
            }

            if (cabang.get(i).left != null) {
                cabang.add(cabang.get(i).left);
            }
            if (cabang.get(i).right != null) {
                cabang.add(cabang.get(i).right);
            }

        }
    }

    static void add(long val) {
        trie c = root;
        trie temp = new trie(val);

        if (c == null) {
            root = temp;
            besar = temp;
            size++;
            return;
        }

        while (true) {
            if (val < c.val) {
                if (c.left != null) {
                    c = c.left;
                } else {
                    temp.parent = c;
                    c.left = temp;
                        size++;
                    return;
                }
            }
            if (val > c.val) {
                if (c.right != null) {
                    c = c.right;
                } else {
                    temp.parent = c;
                    c.right = temp;
                    if (besar.val < val) {
                        besar = temp;
                    }
                    size++;
                    return;
                }
            }
            if (val == c.val) {
                size--;
                //putuskan
                if (c.parent != null) {
                    long pv = c.parent.val;
                    //c merupakan kanannya parent
                    if (pv < c.val) {
                        if (c.left != null && c.right != null) {
                            join(c.left, c.right);
                            c.left.parent = c.parent;
                            c.parent.right = c.left;
                        } else if (c.left != null) {
                            c.parent.right = c.left;
                        } else if (c.right != null) {
                            c.parent.right = c.right;
                        } else{
                            besar= c.parent;
                            c.parent.right = null;
                        }
                    }
                    //c merupakan kirinya parent
                    if (pv > c.val) {
                        if (c.left != null && c.right != null) {
                            join(c.left, c.right);
                            c.left.parent = c.parent;
                            c.parent.left = c.left;
                        } else if (c.left != null) {
                            c.parent.left = c.left;
                        } else if (c.right != null) {
                            c.parent.left = c.right;
                        }else{
                            c.parent.left = null;
                        }
                    }
                } else {
                    root = null;
                    besar=null;
                }

                //add
                add(val + 1);
                return;
            }
        }
    }
    static void cetak(trie n){
        if(n!=null){
            cetak(n.left);
            print("%d ",n.val);            
            cetak(n.right);
        }
        
    }
    public static void solve3(){
        int n  =  getInt();
        HashSet<Long> d = new HashSet<Long>();
        Long data[] = getLongArr();
        long max = -1;
        for(long l : data){
            while(d.contains(l)){
                d.remove(l);
                ++l;
            }
            if(l > max){
                max = l;
            }
            d.add(l);
        }
        print(max- d.size() + 1);
    }

    public static void solve2() {
        int n = getInt();

        Long data[] = getLongArr();
        if (n == 1) {
            print(data[0]);
            return;
        }
        for(long i  : data){
            if(besar!= null && i>besar.val){
                trie temp = new trie(i);
                temp.parent = besar;
                besar.right=temp;
                besar = temp;
                size++;
                //cetak(root);
               // print("");
                continue;
            }
            add(i);
            //cetak(root);
            //print("");
        }
        //cetak(root);
        
        //print(besar.val+" "+size);
        print(besar.val - size + 1);
        
    }

    public static void solve() {
        int n = getInt();
        //print(Math.pow(2, 2000000000));


        Long data[] = getLongArr();

        if (n == 1) {
            print(data[0]);
            return;
        }

        ArrayList<Long> hehe = new ArrayList<Long>();
        hehe.add(data[0]);


        for (int i = 1; i < n; i++) {
            //print("SEBELUM");
            //print(hehe);
            long v = data[i];
            if (hehe.get(hehe.size() - 1) < v) {
                hehe.add(v);
            } else if (hehe.get(hehe.size() - 1) == v) {
                hehe.set(hehe.size() - 1, v + 1);
                //print(hehe);
            } else if (hehe.get(hehe.size() - 1) > v) {
                int index = Collections.binarySearch(hehe, v);
                if (index >= 0) {
                    hehe.remove(index);
                    v++;
                    index = Collections.binarySearch(hehe, v);
                    while (index >= 0) {
                        hehe.remove(index);
                        ++v;
                        index = Collections.binarySearch(hehe, v);
                    }
                    hehe.add(v);
                } else {
                    hehe.add(v);
                }
                Collections.sort(hehe);
            }
            //print("SESUDAH DIMASUKKAN "+v);
            //print(hehe);
        }
        //(hehe);
        long needed = hehe.get(hehe.size() - 1);

        needed -= hehe.size() - 1;
        print(needed);

    }
}
