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.util.*;
import java.util.Map.Entry;

public class C {

	void run() throws IOException {
		int n = ni();
		TreeMap<Long, Integer> t = new TreeMap<Long, Integer>();
		TreeMap<Long, Integer> q = new TreeMap<Long, Integer>();
		for (int i = 0; i < n; i++) {
			add(t, ni());
		}
		while (t.size() > 0) {
			Entry<Long, Integer> e = t.pollFirstEntry();
			long k = e.getKey(), v = e.getValue(), x = 0;
			// tr(k + " " + v);
			while (v > 0) {
				if (v % 2 == 1) {
					if (x != 0) {
						add(t, k + x);
					} else {
						add(q, k + x);
					}
				}
				x++;
				v /= 2;
			}
		}
		long ans = 0;
		// add(q, -1);
		// long max = q.pollLastEntry().getKey();
		long min = -1;
		while (q.size() > 0) {
			Entry<Long, Integer> e = q.pollFirstEntry();
			long k = e.getKey(), v = e.getValue();
			ans += k - min - 1;
			min = k;
			// tr(e.getKey() + " " + e.getValue());
		}
		pw.println(ans);
	}

	void add(TreeMap<Long, Integer> t, long k) {
		if (t.containsKey(k)) {
			int v = t.remove(k);
			t.put(k, v + 1);
		} else {
			t.put(k, 1);
		}
	}

	int[] na(int a_len) throws IOException {
		int[] _a = new int[a_len];
		for (int i = 0; i < a_len; i++)
			_a[i] = ni();
		return _a;
	}

	int[][] nm(int a_len, int a_hei) throws IOException {
		int[][] _a = new int[a_len][a_hei];
		for (int i = 0; i < a_len; i++)
			for (int j = 0; j < a_hei; j++)
				_a[i][j] = ni();
		return _a;
	}

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

	int ni() throws IOException {
		return Integer.parseInt(next());
	}

	String nl() throws IOException {
		return br.readLine();
	}

	void tr(String debug) {
		if (!OJ)
			pw.println(" " + debug);
	}

	static PrintWriter pw;
	static BufferedReader br;
	static StringTokenizer st;
	static boolean OJ;

	public static void main(String[] args) throws IOException {
		long timeout = System.currentTimeMillis();
		OJ = System.getProperty("ONLINE_JUDGE") != null;
		pw = new PrintWriter(System.out);
		br = new BufferedReader(OJ ? new InputStreamReader(System.in) : new FileReader(new File("C.txt")));

		while (br.ready())
			new C().run();
		if (!OJ) {
			pw.println();
			pw.println(System.currentTimeMillis() - timeout);
		}
		br.close();
		pw.close();
	}

}