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 2^a1, 2^a2, ..., 2^an on a piece of paper. Now he wonders, what minimum number of integers of form2^b (b ≥ 0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2^v - 1 for some integer v (v ≥ 0).

Help Ivan, find the required quantity of numbers.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵). The second input line contains n space-separated integers a1, a2, ..., an(0 ≤ ai ≤ 2·10⁹). 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 2³ - 1 = 7.

In the second sample you need to add numbers 2⁰, 2¹, 2².

 

题目大意：给你一个n表示有n个ai，ai表示2^ai。问你需要再加几个形如2^b的数，让他们的总和为2^v-1。

解题思路：首先看数据范围，如果想通过暴力是完全行不通的。所以观察所求的2^v-1，这个数必然是由2进制所有都为1组成的。然而他给你ai是2^ai，是2的次方。所以我们合并相同的ai，2^a+2^a=2*(2^a)=2^(a+1)，所以如果有相同的，让ai自加，然后放入set容器中判断，如果还有相同的，从容器中删除后再将该数自加，重复，直到没有相同的该数，放入set中。最后用最大的a减去set的大小即为答案。可以自己模拟一下过程，就能理解了。

 

#include
           
            using namespace std;#define LL long longint main(){    int Maxn,a;    int n,i,j,k;    while(scanf("%d",&n)!=EOF){        set
            
             S;        S.clear();        Maxn=0;        for(i=0;i
             
              a?Maxn:a;        }        printf("%d\n",Maxn+1-S.size());    }    return 0;}