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 p305C {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		try { st = new StringTokenizer(bf.readLine()); } catch(Exception ex) {}

		int n = Integer.parseInt(st.nextToken());
		ArrayList<Integer> al = new ArrayList<>();

		try { st = new StringTokenizer(bf.readLine()); } catch(Exception ex) {}
		al.add(Integer.parseInt(st.nextToken()));
		for(int i=1, pos=1; i<n; ++i, ++pos) {
			int token = Integer.parseInt(st.nextToken());
			al.add(token);

			boolean changed = true;
			while(changed) {
				changed = false;

				if(pos > 0 && al.get(pos-1) > al.get(pos)) {
					int tmp = al.get(pos-1);
					al.set(pos-1, al.get(pos));
					al.set(pos, tmp);
					changed = true;
				}

				if(pos > 0 && al.get(pos).intValue() == al.get(pos-1).intValue()) {
					int tmp = al.get(pos);
					al.remove(pos);
					al.remove(pos-1);

					al.add(tmp+1);
					--pos;
					changed = true;
				}

				if(pos > 1 && al.get(pos-1).intValue() == al.get(pos-2).intValue()) {
					int tmp = al.get(pos-1);
					al.remove(pos-1);
					al.remove(pos-2);

					al.add(tmp+1);
					--pos;
					changed = true;
				}
			}	

		}


		int res = al.get(0);
		for(int i=1; i<al.size(); ++i) {
			res += al.get(i) - al.get(i-1) - 1;
		}

		System.out.println(res);

	}
}