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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class C {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
	public void solve() throws IOException {		
		int N = nextInt();
		int[] a = new int[N];
		for(int i = 0; i < N; i++)
			a[i] = nextInt();
		
		int ans = a[0];
		int cur = 0;
		int count = 0;
		while( cur < N){
			int cur2 = cur;
			while( cur2 < N-1 && a[cur2+1] == a[cur] )
				cur2++;								
			count = count + (cur2 - cur + 1);			
			if( cur2 == N-1){					
				while( count > 0){
					if( (count & 1) == 0) ans++;
					count >>= 1;
				}
			}
			else{
				int diff = a[cur2+1] - a[cur];				
				for(int i = 0; i < diff; i++){
					if( (count & 1) == 0) ans++;
					count >>= 1;				
					
					if( count == 0) {
						ans += (diff-i-1); 
						
						break;						
					}
				}								
			}
			cur = cur2 + 1;			 
		}
		out.println( ans );
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new C().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

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

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

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

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

}
