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 static java.lang.Math.*;
public class ProblemC {
    void run() {
        FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		TreeMap<Long,Integer> a = new TreeMap<Long,Integer>();
		for (int i = 0; i < n; ++i) {
			add(a, sc.nextLong());
		}
		int answer = 0;
		long prev = -1;
		while (!a.isEmpty()) {
			long x = a.firstKey();
			int count = a.get(x);
			a.remove(x);

			if (count < 2) {
				answer += max(0, x - prev - 1);
				prev = x;
				if (count == 0) {
					++answer;
				}
			}
			else {
				while (count > 0) {
					if (count % 2 == 1) {
						add(a, x);
					}
					count /= 2;
					++x;
				}
			}
		}
		p("%d\n", answer);
    }

	void add(TreeMap<Long,Integer> a, long x) {
		int val = a.containsKey(x) ? a.get(x) : 0;
		a.put(x, val + 1);
	}

    boolean debug = false;
    void p(String f, Object...params) {
        System.out.printf(f, params);
    }
    void d(Object...params) {
        if (debug) {
            p("DEBUG: %s\n", Arrays.deepToString(params));
        }
    }
    static void die() {
        throw new RuntimeException();
    }
    void timeout() {
        for (int x = 0; ; ++x);
    }
    String join(Collection<?> s, String delimiter) {
        StringBuilder builder = new StringBuilder();
        Iterator<?> iter = s.iterator();
        while (iter.hasNext()) {
            builder.append(iter.next());
            if (iter.hasNext()) {
                builder.append(delimiter);
            }
        }
        return builder.toString();
    }
    public ProblemC(String[] args) {
        if (args.length > 0 && args[0].equals("debug")) {
            debug = true;
        }
    }
    public static void main(String[] args) {
        new ProblemC(args).run();
    }

    private static class FastScanner {
      private BufferedReader in;
      private StringTokenizer tok;
      public FastScanner(InputStream inputstream) {
        in = new BufferedReader(new InputStreamReader(inputstream));
        tok = null;
      }
      private void tokenizeLine() {
        try {
          String line = in.readLine();
          if (line == null) die();
          tok = new StringTokenizer(line);
        } catch (IOException e) {
          die();
        }
      }
      public String next() {
        while (tok == null || !tok.hasMoreTokens()) {
          tokenizeLine();
        }
        return tok.nextToken();
      }
      public boolean hasNextLine() {
        if (tok == null) {
          try {
            tokenizeLine();
          }
          catch (Exception e) {
            return false;
          }
        }
        return true;
      }
      public String nextLine() {
        if (tok == null) {
          tokenizeLine();
        }
        String ret = tok.hasMoreTokens() ? tok.nextToken("\n"): "";
        tok = null;
        return ret;
      }
      public int nextInt() {
        return Integer.parseInt(next());
      }
      public long nextLong() {
        return Long.parseLong(next());
      }
      public double nextDouble() {
        return Double.parseDouble(next());
      }
    }
}
