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。