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.*;

public class contest184C {
	public static void main(String[] args)throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(rd.readLine());
		int n = Integer.parseInt(tk.nextToken());
		int[ ]arr = new int[n];
		pair[] mas = new pair[n];
		tk = new StringTokenizer(rd.readLine());
		int counter = 1;
		int indexer = 0;
		arr[0] = Integer.parseInt(tk.nextToken());
		
		for (int i = 1; i < arr.length; i++) {
			arr[i] =  Integer.parseInt(tk.nextToken());
			//System.out.println(arr[i]);
			if(arr[i] == arr[i - 1]){
				counter ++;
				continue;
			}
			pair p = new pair(); p.value = arr[i - 1];
			p.quant = counter;
			mas[indexer] = p;
			indexer ++;
			counter = 1;
		}
		
		pair p = new pair(); p.value = arr[arr.length - 1];
		p.quant = counter;
		mas[indexer] = p;
		
		ArrayList<Integer> ar = new ArrayList<Integer>();
		for (int i = 0; i < mas.length; i++) {
			if(mas[i] == null) break;
			while(true){
				pair pr = mas[i];
				if(pr.quant == 1) {
					ar.add(pr.value);
					break;
				}
				if(pr.quant % 2 == 1) ar.add(pr.value);
				if(i + 1 < arr.length && mas[i + 1] != null){
					if(mas[i + 1].value == pr.value + 1){
						mas[i + 1].quant += pr.quant/2;
						break;
					}
				}
				pr.value ++;
				pr.quant /= 2;
				
				
			}
			
		}
		
		//System.out.println(ar);
		int max = ar.get(ar.size() - 1);
		System.out.println(max - (ar.size() - 1));
		
	}
}
class pair{
	int value;
	int quant;
	
}