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.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class C {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] ar = new long[n];
		HashMap<Long, Long> map = new HashMap<Long, Long>();
		for(int i=0;i<n;i++) ar[i] = Integer.valueOf(sc.next());
		for(int i=0;i<n;i++) {
			if(map.containsKey(ar[i])) map.put(ar[i], map.get(ar[i])+1L);
			else map.put(ar[i], 1L);
		}
		HashSet<Long> set = new HashSet<Long>();
		PriorityQueue<P> que = new PriorityQueue<P>();
		for(Map.Entry<Long, Long> entry: map.entrySet()) que.add(new P(entry.getKey(), entry.getValue()));
		for(;!que.isEmpty();) {
			P p = que.remove();
			if(p.c==0) continue;
			if(p.c%2!=0) {
				if(set.contains(((Long)p.v))) {
					set.remove(((Long)p.v));
					que.add(new P(p.v+1, 1));
				}
				else set.add(p.v);
			}
			que.add(new P(p.v+1, p.c/2));
		}
		long max = 0;
		for(long v: set) max = max(max, v);
		System.out.println(max - set.size()+1);
	}
	
	class P implements Comparable<P>{
		long v, c;
		P(long v, long c) {
			this.v = v;
			this.c = c;
		}
		public int compareTo(P p) {
			return v - p.v>0? 1:-1;
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new C().run();
	}
}