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.*;
import java.lang.*;
import java.util.*;
import java.text.*;


public class Main {
	

	public static void main(String[] args) throws IOException {

		
		//BufferedReader cin = new BufferedReader(new FileReader("test.txt"));
		 BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	
		
		String line;
		StringTokenizer st;
		
		line = cin.readLine();
		st = new StringTokenizer(line);
		
		int n = Integer.parseInt(st.nextToken());
		//int a = Integer.parseInt(st.nextToken());
		//int b = Integer.parseInt(st.nextToken());
		
		//int[] list = new int[n];
		//Arrays.fill(list,0);
		Set<Integer> set = new HashSet<Integer>();
		
		line = cin.readLine();
		st = new StringTokenizer(line);
		int t;
		int count=0;
		int max=0;
		for(int i=0;i<n;i++){
			t=Integer.parseInt(st.nextToken());
			while(set.contains(t)){
				set.remove(t);
				t++;
				count--;
			}
			set.add(t);
			if(t>max)max=t;
			count++;
		}
		
		int ans = max-count+1;
		System.out.println(ans);
	


		cin.close();
	}

}