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.
//package Round184;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Do Quoc bao
 */
public class ProblemC {
    public static void main(String[] args) {
        try {
            Reader.init(System.in);
            int n=Reader.nextInt();
            TreeMap<Integer,Integer> Mp = new TreeMap<>();
            Mp.put(0, 1);
            for (int i=0;i<n;++i) {
                int x = Reader.nextInt();
                if (Mp.containsKey(x)) {
                    int k =Mp.get(x);
                    k++;
                    Mp.remove(x);
                    Mp.put(x, k);
                }
                else Mp.put(x, 1);
            }
            int kq=0;
            boolean isEnd=false;
            while (isEnd==false) {
                Set<Integer> S = new TreeSet<>(Mp.keySet());
                isEnd=true;
                for (int entry:S) {
                    if (Mp.get(entry)>1) {
                        int Val=Mp.get(entry);
                        int newVal=Val%2;
                        int nextVal=Val/2;
                        int nextKey=entry+1;
                        
                        if (newVal==0) Mp.remove(entry);
                        else {
                            Mp.remove(entry);
                            Mp.put(entry, newVal);
                        }
                        
                        if (Mp.containsKey(nextKey)) {
                            int oldVal=Mp.get(nextKey);
                            Mp.remove(nextKey);
                            Mp.put(nextKey, oldVal+nextVal);
                        }
                        else {
                            isEnd=false;
                            Mp.put(nextKey, nextVal);
                        }
                    }
                }
            }
            
            Set<Integer> S = new TreeSet<>(Mp.keySet());
            int dau=-1;
            if (S.size()==1) System.out.println(0);
            else
            {
            for (int key:S) {
                if (key==0) {
                    ++kq;
                    dau=0;
                }
                else {
                    if (dau==-1) {
                        ++kq;
                        kq=kq+(key-dau-1);
                        dau=key;
                    }
                    else {
                        kq=kq+(key-dau-1);
                        dau=key;
                    }
                }
            }
            System.out.println(kq);
            }
            
        } catch (IOException ex) {
            Logger.getLogger(ProblemC.class.getName()).log(Level.SEVERE, null, ex);
        }
        
    }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
	
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}