#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:64000000")
int a, s, d, f, g, q, w, e, r, h, j;
int inf = pow(10.0, 9.0) + 7;
struct treap {
  int x, y, l, r, z;
};
struct qwe {
  int l, r;
};
vector<treap> ar;
int merge1(int tl, int tr) {
  if (tl == 0) {
    return tr;
  }
  if (tr == 0) {
    return tl;
  }
  if (ar[tl].y >= ar[tr].y) {
    ar[tl].r = merge1(ar[tl].r, tr);
    return tl;
  } else {
    ar[tr].l = merge1(tl, ar[tr].l);
  }
}
vector<qwe> arz;
bool qaz(qwe a, qwe s) { return a.l < s.l; }
int main() {
  arz.reserve(1000000);
  cin >> a;
  qwe o;
  for (s = 0; s < a; ++s) {
    cin >> d;
    if (arz.size() == 0) {
      o.l = d;
      o.r = 1;
      arz.push_back(o);
    } else {
      if (arz[arz.size() - 1].l == d) {
        ++arz[arz.size() - 1].r;
      } else {
        o.l = d;
        o.r = 1;
        arz.push_back(o);
      }
    }
  }
  for (d = 0; d < 20; ++d) {
    f = 0;
    g = arz.size();
    for (s = 0; s < g; ++s) {
      if (arz[s].r > 1) {
        f = 1;
        if (s == g - 1) {
          o.l = arz[s].l + 1;
          o.r = arz[s].r / 2;
          arz.push_back(o);
          arz[s].r = arz[s].r % 2;
          ++g;
        } else {
          if (arz[s].l == arz[s + 1].l - 1) {
            arz[s + 1].r += arz[s].r / 2;
            arz[s].r %= 2;
          } else {
            o.l = arz[s].l + 1;
            o.r = arz[s].r / 2;
            arz.push_back(o);
            arz[s].r = arz[s].r % 2;
          }
        }
      }
    }
    sort(arz.begin(), arz.end(), qaz);
    if (f == 0) {
      d = 20;
    }
  }
  f = arz[0].l;
  if (arz[0].r == 0) {
    ++f;
  }
  for (s = 0; s < arz.size() - 1; ++s) {
    f += arz[s + 1].l - arz[s].l - 1;
    if (arz[s + 1].r == 0) {
      ++f;
    }
  }
  cout << f;
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:64000000")
int a, s, d, f, g, q, w, e, r, h, j;
int inf = pow(10.0, 9.0) + 7;
struct treap {
  int x, y, l, r, z;
};
struct qwe {
  int l, r;
};
vector<treap> ar;
int merge1(int tl, int tr) {
  if (tl == 0) {
    return tr;
  }
  if (tr == 0) {
    return tl;
  }
  if (ar[tl].y >= ar[tr].y) {
    ar[tl].r = merge1(ar[tl].r, tr);
    return tl;
  } else {
    ar[tr].l = merge1(tl, ar[tr].l);
  }
}
vector<qwe> arz;
bool qaz(qwe a, qwe s) { return a.l < s.l; }
int main() {
  arz.reserve(1000000);
  cin >> a;
  qwe o;
  for (s = 0; s < a; ++s) {
    cin >> d;
    if (arz.size() == 0) {
      o.l = d;
      o.r = 1;
      arz.push_back(o);
    } else {
      if (arz[arz.size() - 1].l == d) {
        ++arz[arz.size() - 1].r;
      } else {
        o.l = d;
        o.r = 1;
        arz.push_back(o);
      }
    }
  }
  for (d = 0; d < 20; ++d) {
    f = 0;
    g = arz.size();
    for (s = 0; s < g; ++s) {
      if (arz[s].r > 1) {
        f = 1;
        if (s == g - 1) {
          o.l = arz[s].l + 1;
          o.r = arz[s].r / 2;
          arz.push_back(o);
          arz[s].r = arz[s].r % 2;
          ++g;
        } else {
          if (arz[s].l == arz[s + 1].l - 1) {
            arz[s + 1].r += arz[s].r / 2;
            arz[s].r %= 2;
          } else {
            o.l = arz[s].l + 1;
            o.r = arz[s].r / 2;
            arz.push_back(o);
            arz[s].r = arz[s].r % 2;
          }
        }
      }
    }
    sort(arz.begin(), arz.end(), qaz);
    if (f == 0) {
      d = 20;
    }
  }
  f = arz[0].l;
  if (arz[0].r == 0) {
    ++f;
  }
  for (s = 0; s < arz.size() - 1; ++s) {
    f += arz[s + 1].l - arz[s].l - 1;
    if (arz[s + 1].r == 0) {
      ++f;
    }
  }
  cout << f;
  return 0;
}

```