题目描述

给出非负整数序列 $a_1\le\cdots\le a_n$，它对应的数列为 $2^{a_1},\ldots,2^{a_n}$。允许加入任意多个形如 $2^x$ 的数，其中 $x$ 为非负整数。求至少加入多少个数，才能使所有数的和为 $2^v-1$，其中 $v$ 为某个非负整数。

输入格式

第一行 $n$，第二行 $n$ 个指数。

输出格式

输出至少加入的数的个数。

样例

4
0 1 1 1

0

1
3

3

数据范围

$1\le n\le10^5$，$0\le a_i\le2\times10^9$，序列单调不降。