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.
#include <bits/stdc++.h>
using namespace std;
string getBin(long long num) {
  string res = "";
  while (num) {
    res += ((num & 1) + '0');
    num /= 2;
  }
  return res;
}
void main2() {
  int n;
  n = ({
    int t;
    scanf("%d", &t);
    t;
  });
  long long a[n];
  for (int i = 0, _n = n; i < _n; i++)
    a[i] = ({
      long long t;
      scanf("%lld", &t);
      t;
    });
  map<int, int> my;
  for (int i = 0, _n = n; i < _n; i++) my[a[i]]++;
  map<long long, int> f;
  for (__typeof((my).begin()) it = (my).begin(); it != (my).end(); ++it) {
    int x = (*it).second;
    int num = (*it).first;
    string s = getBin(x);
    for (int i = 0, _n = (int)(s).size(); i < _n; i++) {
      if (s[i] == '1') {
        if (f[(long long)i + num] == 0)
          f[(long long)i + num] = 1;
        else {
          long long k = 1;
          long long temp = (long long)(i + num) * k;
          while (f[temp] == 1) {
            k *= 2ll;
            f[temp] = 0;
            temp = (long long)(i + num) * k;
          }
          f[temp] = 1;
        }
      }
    }
  }
  long long mx = 0, sz = 0;
  for (__typeof((f).begin()) it = (f).begin(); it != (f).end(); ++it) {
    if ((*it).second != 0) sz++;
    mx = max(mx, (*it).first);
  }
  long long cnt = (mx + 1) - (sz);
  printf("%lld\n", cnt);
}
int main() { main2(); }
