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.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Map.Entry;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class C {
	public static void main(String[] args) throws Exception {
		int cnt = nextInt();
		int[] ar = new int[cnt];
		for (int i = 0; i < cnt; i++) {
			ar[i] = nextInt();
		}
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		ArrayList<Point> entries = new ArrayList<Point>();
		for (int i = 0; i < cnt; i++) {
			int prev = ar[i];
			int cur = prev;
			int eqCnt = 1;
			int j = i + 1;
			while (j < cnt) {
				cur = ar[j];
				if (cur == prev) {
					eqCnt++;
				} else
					break;
				j++;
			}
			entries.add(new Point(prev, eqCnt));
			i = j - 1;
		}
		Collections.sort(entries, new Comparator<Point>() {
			public int compare(Point p1, Point p2) {
				return new Integer(p1.x).compareTo(p2.x);
			}
		});
		int exist = 0;
		int maxPower = 0;
		for (int i = 0; i < entries.size(); i++) {
			Point point = entries.get(i);
			if (map.size() > 0) {
				if (map.firstKey() < point.x) {
					Entry<Integer, Integer> e = map.pollFirstEntry();
					point = new Point(e.getKey(), e.getValue());
					i--;
				} else if (map.firstKey() == point.x) {
					Entry<Integer, Integer> e = map.pollFirstEntry();
					point.y += e.getValue();
				}
			}
			if (point.y >= 1) {
				int val = point.y;
				while (val > 1) {
					int j = 1;
					int power = point.x - 1;
					for (; j <= val; j <<= 1) {
						power++;
					}
					j >>= 1;
					val -= j;
					if (map.containsKey(power)) {
						map.put(power, map.get(power) + 1);
					} else {
						map.put(power, 1);
					}
				}
				if (val == 1) {
					maxPower = Math.max(maxPower, point.x);
					exist++;
				}
			}
			if (i == entries.size() - 1) {
				while (!map.isEmpty()) {
					Entry<Integer, Integer> e = map.pollFirstEntry();
					entries.add(new Point(e.getKey(), e.getValue()));
				}
			}
		}
		System.out.println(maxPower + 1 - exist);
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer st = new StringTokenizer("");

	static int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

	static String next() throws Exception {
		while (true) {
			if (st.hasMoreTokens()) {
				return st.nextToken();
			}
			String s = br.readLine();
			if (s == null) {
				return null;
			}
			st = new StringTokenizer(s);
		}
	}
}
