Ivan and Powers of Two（杂）

C. Ivan and Powers of Two

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Sample test(s)

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.

 

       题意：

       给出 n（1 ~ 100000）代表有 n 个数，后给出 n 个数，代表 2 ^ ai，加和之后，问要添加多少个 2 ^ i 使变成 2 ^ v -1。

 

       思路：

       因为 2 ^ a + 2 ^ a = 2 ^ (a + 1)，所以当某个数出现 2 次以上的时候可以通过合并不断得到新的数，并且保证每个数都出现一次。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

int main() {

    int n;
    set<int> s;
    scanf("%d", &n);

    int max_num = -1;
    while (n--) {
        int ans;
        scanf("%d", &ans);
        while (s.count(ans)) {
            s.erase(ans);
            ++ans;
        }
        s.insert(ans);
        max_num = max(max_num, ans);
    }

    printf("%d\n", max_num - s.size() + 1);

    return 0;
}