Ivan and Powers of Two

题意翻译

有一个由 $n$ 个非负整数组成的序列 $a_1$ 到 $a_n$，这个序列保证单调不降。接着，小华将上述序列作为2的次幂，写下了另一个序列：2的 $a_1$ 次幂到2的 $a_n$ 次幂。 现在他想知道，最少要在这个序列中添加多少个形式为 $2^x$ 的数（$x$ 为非负整数），才能使这个序列所有整数的和为 $2^v-1$，其中 $v$ 为某个非负整数。

题目描述

Ivan has got an array of $ n $ non-negative integers $ a_{1},a_{2},...,a_{n} $ . Ivan knows that the array is sorted in the non-decreasing order. Ivan wrote out integers $ 2^{a_{1}},2^{a_{2}},...,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 integer $ v $ $ (v>=0) $ . Help Ivan, find the required quantity of numbers.

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ). The second input line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ $ (0<=a_{i}<=2·10^{9}) $ . It is guaranteed that $ a_{1}<=a_{2}<=...<=a_{n} $ .

输出格式

Print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

4
0 1 1 1

输出样例 #1

0

输入样例 #2

1
3

输出样例 #2

3

说明

In the first sample you do not need to add anything, the sum of numbers already equals $ 2^{3}-1=7 $ . In the second sample you need to add numbers $ 2^{0},2^{1},2^{2} $ .