P96280

指数序列

难度 未定
讨论 统计 5通过 7提交 71.4%通过率 旧版界面
时间限制 1 秒 内存限制 256 MB

题目描述

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

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

输入

第 1 行包括 1 个正整数 n(1≤n≤105 )。

第 2 行包括 n 个由空格隔开的整数a1,a2,...an。其中0≤a^i≤10^9,保证a1≤a2≤,...≤an

 

输出

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

样例

样例 1
输入
4
0 1 1 1
输出
0
样例 2
输入
1
3
输出
3

提示

【样例解释】

1565424286574.png

来源

课课通

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交