题目描述

伊凡在在纸上写下了一个由 n 个非负整数组成的序列 $a_1 , a_2 , a_3 , ... , a_n$ 。这个序列保证单调不降。

接着，伊凡又在纸上写下了另一个序列$2^{a_1} , 2^{a_2} , 2^{a_3} , ... , 2^{a_n}$ 。现在他想知道，最小要在这个序列中添加多少个形式为 $2^x$ 的数( x 为非负整数 )，才能使这个序列所有整数的和为 $2^v-1$ ，其中 v 为某个非负整数。

输入格式

第 1 行 1 个正整数 n ( 1 <= n <= ${10}^5$ );

第 2 行包括 n 个由空格隔开的整数 $a_1 , a_2 , a_3 , ... , a_n$ 。其中， 0 <= $a_i$ <= 2*$10^9$，保证 $a_1$ <= $a_2$ <= $a_3$ ... <= $a_n$ 。

输出格式

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

样例

4
0 1 1 1

0

1
3

3

样例解释

在第一个样例中不需要添加任何数，因为 $2^0+2^1+2^1+2^1$=$2^0+2^1+2*2^1$=$2^0+2^1+2^2$=$1+2+4=7$=$2^3-1$ 。

在第二个样例中，需要至少添加 3 个数，分别为 $2^0 , 2^1 , 2^2$ 。