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.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class C {
	
	public static void main(String [] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer tokenizer = new StringTokenizer(br.readLine());
		
		List<Long> a = new ArrayList<Long>();
		
		TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
		
		for(int i=0; i<N; i++) { 
			long num =Integer.parseInt(tokenizer.nextToken()); 
			a.add(num);
			
			Integer val = map.get(num);
			
			if(val == null) val = 0;
			
			val++;
			
			map.put(num, val);
		}
		
		ArrayList<Long> sols = new ArrayList<Long>();
		for(int i=0; i<a.size(); i++) { 
			
			long num = a.get(i);
			
			int counter = 0;
			
			boolean once = false;
			while((counter = map.get(num)) > 1) { 
				
				Long nextNum = num + 1; 
				
				
				Integer nextVal = map.get(nextNum);
				if(nextVal == null) nextVal = 0;
				
				nextVal++;
				map.put(nextNum, nextVal);
				map.put(num, counter-2);
				
				if(!once) { 
					once = true;
					a.add(nextNum);
				}
			}
			
			if(map.get(num) == 0) {
				map.remove(num);
			}
			else {
				sols.add(num);
			}
			
			while(i < a.size() && a.get(i) == num) i++;
			
			i--;
		}
		
		
		
		Long firstEntry = map.firstKey();
		boolean hasZero = (firstEntry == 0);
		
		Long lastKey = 0l;
		if(!hasZero) { 
			lastKey = -1l;
		}
		Long totalCounter = 0l;
		for(Long key : map.keySet()) { 
			//System.out.println("key: " + key);
			if(key == 0) { 
				continue;
			}
			totalCounter += key - 1 - lastKey;
			//System.out.println("key: " + key);
			lastKey = key;
		}
		
		System.out.println(totalCounter);


	}

}