題干：

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?nspace-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.

題目大意：（可以練讀題）

? ?給你n個(gè)數(shù)a1,a2....an，分表代表2^a1,2^a2....2^an。現(xiàn)在讓你添加一些數(shù)（假設(shè)num個(gè)），使2^a1 + 2^a2 + ... + 2^an + ... + 2^anum 的和為二進(jìn)制的全1數(shù)（題目中敘述是存在一個(gè)b，s.t. 數(shù)字 = 2^b-1）。求num的最小值

解題報(bào)告：

? 推出來(lái)，需要的數(shù)恰好就是最終集合合并后的剩下缺少的元素之后（不難證明吧貌似2333），接下來(lái)就是怎么維護(hù)這個(gè)集合的元素了。

? 這題可以貪心，用pq暴力合并，別用multiset+set、、、會(huì)炸的（不是炸在迭代器上而是炸在多次的insert上）、

? 當(dāng)然還有更好的做法那就是直接set，然后讀入的同時(shí)就維護(hù)set中的元素就可以了，最后直接輸出一個(gè)值就是我們需要的那個(gè)值了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; set<ll> ss; int main() {int n;ll tmp,maxx = -1;cin>>n;for(int i = 1; i<=n; i++) {scanf("%lld",&tmp);while(ss.find(tmp) != ss.end()) {ss.erase(tmp);tmp++;}ss.insert(tmp);maxx = max(maxx,tmp);} printf("%lld\n",maxx + 1 - ss.size());return 0 ;}

錯(cuò)誤代碼：（這樣寫思路是沒錯(cuò)的就是insert的時(shí)候需要insert? ?tmp/2 這么多個(gè)，所以時(shí)間效率還是不高，改成map可能會(huì)好一點(diǎn)）（剛開始不是+1，，是+tmp/2，這樣是一定錯(cuò)的，因?yàn)檫@是冪次關(guān)系啊不是線性的、、）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n; ll tmp; multiset<ll> ms; set<ll> s; ll a[MAX]; int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i),ms.insert(a[i]),s.insert(a[i]);for(set<ll> :: iterator it = s.begin(); it != s.end();) { // while(ms.count(*it) >= 2) { // ms.erase(ms.find((*it))); // ms.erase(ms.find((*it))); // ms.insert((*it)+1); // s.insert((*it)+1); // if(ms.find((*it)) == ms.end()) s.erase((*it)); // } // ++it;tmp = ms.count((*it));if(tmp % 2 == 1) {s.insert((*it) + 1);ms.erase(*it);ms.insert(*it);ms.insert((*it) + 1);} else {ms.erase((*it));s.insert((*it) + 1);ms.insert((*it) + 1);s.erase(*it);}++it;}multiset<ll> :: iterator mit = ms.end();--mit; // cout << *mit<< endl;ll ans = (*mit) - s.size() + 1;cout << ans << endl;return 0 ; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 305C】Ivan and Powers of Two（思维，STL，set，优先队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。