← 返回题目列表

Codeforces · 305/C

C. 伊万和二的幂

中文机器翻译题面 查看原题

Ivan 得到了一个由 n 个非负整数 a1, a2, ..., an 组成的数组。 Ivan 知道数组是按非降序排序的。

Ivan 在一张纸上写下了整数 2a1, 2a2, ..., 2an。现在他想知道,需要将多少个 2b (b ≥ 0) 形式的整数添加到这张纸上,以便对于某个整数 v (v ≥ 0),写在纸上的所有整数的总和等于 2v - 1。

帮助Ivan,找到所需的数字数量。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二个输入行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 2·109)。保证a1 ≤ a2 ≤ ... ≤ an。

输出

打印一个整数——问题的答案。

示例

输入 #1

4
0 1 1 1

输出 #1

0

输入 #2

1
3

输出 #2

3

注意

在第一个示例中,您不需要添加任何内容,数字之和已经等于 23 - 1 = 7。

在第二个示例中,您需要添加数字 20、21、22。