Extra
Time
2015.8.12 noip模拟赛——迷之阶梯ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้ Time:1s Memory:50M AC:40% Submit:10

题目描述

XX 需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法,否则就无法登上阶梯。它要求的方法有以下三个限制:

1. 如果下一步阶梯的高度只比当前阶梯高1,则可以直接登上。

2. 除了第一步阶梯外,都可以从当前阶梯退到前一步阶梯。

3. 当你连续退下 k 后,你可以一次跳上不超过当前 阶梯高度 2^k 的阶梯。

比如说你现在位于第 j步阶梯,并 且是从第j+k步阶梯退下来的。那么你可以跳到高度不 超过当前阶梯高度 + 2^k 的任何一步阶梯。

跳跃这一次只 算一次移动。

开始时小队在第 1 步阶梯。

由于时间紧迫,小 Z 需要计算 出登上迷之阶梯的最少移动次数。

输入格式

第 1 行:一个整数 N,表示阶梯步数;

第 2 行:N 个整数(每两个之间有 1 个空格),依次为每层阶梯的高度,保证递增。

输出格式

1 行,一个整数,如果能登上阶梯,输出最小步数, 否则输出-1。

样例输入

5

0 1 2 3 6

样例输出

7

数据规模

对于 50%的数据:1 <= N <= 20;

对于 100%的数据:1 <= N <= 200;每步阶梯高度不 超过 2^31-1。