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.
import java.util.*;
import java.io.*;
import java.math.*;

public class C {
    public static Scanner scan = new Scanner(System.in);
    public static boolean bg = false;

    public static void main(String[] args) throws Exception {
        int n1 = Integer.parseInt(scan.next());
        HashMap<Long,Long> m1 = new HashMap();
        TreeSet<Long> l1 = new TreeSet();
        for (int i=0;i<n1;i++){
            long temp = Integer.parseInt(scan.next());
            l1.add(temp);
            if (!m1.containsKey(temp) ){
                m1.put(temp, 0l);
            }
            m1.put(temp, m1.get(temp)+1l);
            if (bg) System.out.println(m1);
            if (bg) System.out.println(l1);
            if (bg) System.out.println();
        }
        while (true){
            if (l1.size()==0){
                break;
            }
            long cur = l1.first();
            l1.remove(cur);
            long val = m1.get(cur);
            long add = val/2l;
            long rm = val%2l;
            if (add!=0){
                if (!m1.containsKey(cur+1l)){
                    m1.put(cur+1l, 0l);
                    l1.add(cur+1l);
                }
                m1.put(cur+1l, m1.get(cur+1l)+add);
            }
                
            if (rm!=0l){
                m1.put(cur, rm);
            }
            else {
                m1.remove(cur);
            }
            if (bg) System.out.println(m1);
            if (bg) System.out.println(l1);
            if (bg) System.out.println();
        }
        long max = Long.MIN_VALUE;
        long count = 0;
        for(long e: m1.keySet()){
            if (m1.get(e)==1l){
                count++;
                if (e>max){
                    max=e;
                }
            }
        }
        if (bg) System.out.println("max "+max);
        if (bg) System.out.println("count "+count);
        System.out.println(max+1l-count);
    }
}
