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.lang.*;

public class cf {
    public static void main(String[] args) {
	InputStream inputStream = System.in;
	OutputStream outputStream = System.out;
	InputReader in = new InputReader(inputStream);
	PrintWriter out = new PrintWriter(outputStream);
	Task task=new Task();
	task.run(in,out);
	out.close();
    }
}

class InputReader {
    public BufferedReader br;
    public StringTokenizer st;
    public InputReader(InputStream stream) {
        br=new BufferedReader(new InputStreamReader(stream),32768);
        st=null;
    }
    public String next() {
        while (st==null || !st.hasMoreTokens()) {
            try {
                st=new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }
    public int nextInt() {return Integer.parseInt(next());}
    public long nextLong() {return Long.parseLong(next());}
    public double nextDouble() {return Double.parseDouble(next());}
}

class Task {
    public void run(InputReader in, PrintWriter out) {
	int n=in.nextInt(),target=0,count=0,leftover=0,maximum=0;
	ArrayDeque<Integer> a=new ArrayDeque<Integer>();
	for (int i=0;i<n;i++) {a.addFirst(in.nextInt());}
	while (a.size()>0) {
	    if (a.getLast()==target) {count++;a.removeLast();}
	    if (a.size()==0 || a.getLast()!=target) {
		if (count%2==1) {leftover++;maximum=target;}
		for (int j=0;j<count/2;j++) {a.addLast(target+1);}
		target=(a.size()==0) ? target+1 : a.getLast();
		count=0;
	    }
	}
	out.print(maximum-leftover+1);
    }
}