Ivan and Powers of Two

116 阅读 0 评论 77 点赞

我是靠谱客的博主娇气棉花糖，最近开发中收集的这篇文章主要介绍Ivan and Powers of Two，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Ivan has got an array of n non-negative integers a₁, a₂, ..., a_n. Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers 2^a₁, 2^a₂, ..., 2^a_n on a piece of paper. Now he wonders, what minimum number of integers of form 2^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 integerv (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 nspace-separated integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 2·10⁹). It is guaranteed that a₁ ≤ a₂ ≤ ... ≤ a_n.

Output

Print a single integer — the answer to the problem.

Example

Input

4
0 1 1 1

Output

Input

1
3

Output

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个数都是2的次方，求最小的2的v次方-1是多少

解题思路:用的是单调队列把，次方重复的累加起来，然后判一下最大次方，在此基础上++，就是v，然后求一下

#include<iostream>  
#include<cstdio>
#include<stdio.h>
#include<cstring>  
#include<cstdio>  
#include<climits>  
#include<cmath> 
#include<vector>
#include <bitset>
#include<algorithm>  
#include <queue>
#include<map>
using namespace std;

long long int n, i, head, tail, a[100005], b[100005], c[100005], ans;
int main()
{
	cin >> n;
	for (i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	head = 0; tail = -1;
	for (i = n; i >=1; i--)
	{
		while (head<=tail&&a[i]==b[tail])
		{
			a[i]++;
			tail--;
		}
		b[++tail] = a[i];
	}
	cout << b[head] + 1 - (tail - head + 1) << endl;
	
}