指数序列（map练习4）

题目描述:

伊凡在在纸上写下了一个由n个非负整数组成的序列a1,a2,a3,……,an。这个序列保证单调不降。

接着，伊凡又在纸上写下了另一个序列2^a1,2^a2,2^a3,……,2^an。现在他想知道，最小要在这个序列中添加多少个形式为2^x的数（x为非负整数），才能使这个序列所有整数的和为2^v-1，其中v为某个非负整数。

输入格式:

第1行包括1个正整数n（1<=n<=10^5）。

第2行包括n个由空格隔开的整数a1,a2,a3,……,an。其中，0<=ai<=2*10^9，保证a1<=a2<=a3……<=an。

输出格式:

输出一行一个整数，表示最少在序列中添加数的数量。

样例输入:

样例1：
4
0 1 1 1

样例2：
1
3

样例输出:

样例1：
0

样例2：
3

提示:

在第一个样例中不需要添加任何数，因为2⁰+2¹+2¹+2¹=2⁰+2¹+2*2¹=2⁰+2¹+2²=1+2+4=7=2³-1。 

在第二个样例中，需要至少添加3个数，分别为2⁰，2¹，2²。

建议使用map当hash表，方便解决问题。

时间限制: 500ms
空间限制: 256MB

---