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.
在這里充分用到了set去重的功能。要知道2^n +2^n= 2^(n+1).先輸入x，如果發現x在集合里面，就要把x去掉，然后將x+1存到里面，如果x+1也在里面的話，就去掉將x+2存到里面，這是一個循環的過程。代碼如下：

#include<iostream> #include<cstring> #include<set> #include<cmath> using namespace std;set<int>num; int n;int main() {while(scanf("%d",&n)!=EOF){int a;num.clear(); int maxn=-0x3f3f3f3f;while(n--){scanf("%d",&a);while(num.count(a)){num.erase(a);a++;}num.insert(a);maxn=max(maxn,a);}printf("%d\n",maxn+1-num.size());}}

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Ivan and Powers of Two CodeForces - 305C（set）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。