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 threadpractice;
//import java.text.DecimalFormat;
import java.util.*;
import java.io.*;
//import java.math.BigInteger;

public class Main {
    
    //public static int count;
    public static void main(String args[]) {
        try {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        HashMap<Long,Integer> hm = new HashMap();
        int c = 1;
        
        long prev = Long.parseLong(s[0]);
        Long max = prev;
        for(int i = 1;i<n;i++){
            long current = Long.parseLong(s[i]);
            if(prev==current){
                c++;
            }
            else{
                long next = prev;
                
                
                while(c!=0){
                    if(hm.containsKey(next)){
                    hm.remove(next);
                    c++;
                }
                    if(max<next){
                    max = next;
                }
                if(c%2==0){
                    next++;c = c/2;
                }
                else{
                    hm.put(next,1);
                    c = c/2;
                    next++;
                }
                
                }
                //System.out.println(next+" "+hm);
               c = 1; 
            }
            
            prev = current;
        }
        long next = prev;
        
                
                while(c!=0){
                    if(hm.containsKey(next)){
                    hm.remove(next);
                    c++;
                }
                    if(max<next){
                    max = next;
                }
                if(c%2==0){
                    next++;c = c/2;
                }
                else{
                    hm.put(next,1);
                    c = c/2;
                    next++;
                }
                
                }
                //System.out.println(next+" "+hm);
                //System.out.println(hm);
        System.out.println(max+1-hm.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
   }


