#include <bits/stdc++.h>
using namespace std;
int b[300000], co[300000];
int main() {
  int n, i, a[110000], c = 0, v = 0, cur, prev;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  b[0] = a[0];
  co[0] = 1;
  for (i = 1; i < n; i++) {
    if (a[i] == a[i - 1])
      co[v]++;
    else {
      v++;
      b[v] = a[i];
      co[v] = 1;
    }
  }
  cur = b[0];
  if (co[0] % 2 == 1) c++;
  cur++;
  prev = co[0] / 2;
  i = 1;
  while (i <= v) {
    if (prev == 0) {
      if (co[i] % 2 == 1) c++;
      if (co[i] >= 2)
        prev = co[i] / 2;
      else
        prev = 0;
      cur = b[i] + 1;
      i++;
    } else {
      if (cur != b[i]) {
        if (prev % 2 == 1) c++;
        if (prev >= 2)
          prev = prev / 2;
        else
          prev = 0;
        cur++;
      } else {
        prev += co[i];
        if (prev % 2 == 1) c++;
        if (prev >= 2)
          prev = prev / 2;
        else
          prev = 0;
        cur++;
        i++;
      }
    }
  }
  while (prev != 0) {
    if (prev % 2 == 1) c++;
    if (prev >= 2)
      prev = prev / 2;
    else
      prev = 0;
    cur++;
  }
  printf("%d\n", cur - c);
  return 0;
}

### Prompt

Generate 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;
int b[300000], co[300000];
int main() {
  int n, i, a[110000], c = 0, v = 0, cur, prev;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  b[0] = a[0];
  co[0] = 1;
  for (i = 1; i < n; i++) {
    if (a[i] == a[i - 1])
      co[v]++;
    else {
      v++;
      b[v] = a[i];
      co[v] = 1;
    }
  }
  cur = b[0];
  if (co[0] % 2 == 1) c++;
  cur++;
  prev = co[0] / 2;
  i = 1;
  while (i <= v) {
    if (prev == 0) {
      if (co[i] % 2 == 1) c++;
      if (co[i] >= 2)
        prev = co[i] / 2;
      else
        prev = 0;
      cur = b[i] + 1;
      i++;
    } else {
      if (cur != b[i]) {
        if (prev % 2 == 1) c++;
        if (prev >= 2)
          prev = prev / 2;
        else
          prev = 0;
        cur++;
      } else {
        prev += co[i];
        if (prev % 2 == 1) c++;
        if (prev >= 2)
          prev = prev / 2;
        else
          prev = 0;
        cur++;
        i++;
      }
    }
  }
  while (prev != 0) {
    if (prev % 2 == 1) c++;
    if (prev >= 2)
      prev = prev / 2;
    else
      prev = 0;
    cur++;
  }
  printf("%d\n", cur - c);
  return 0;
}

```