题目描述

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

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

输入数据

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

第 $2$ 行包括 $n$ 个由空格隔开的整数 $a_1$，$a_2$，…，$a_n$。其中，$0≤a_i ≤2×10^9$，保证 $a_1≤a_2≤…≤a_n$。

输出数据

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

4
0 1 1 1

0

1
3

3

样例说明

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

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