Background

After many days of work by the mathematicians of the Earth Defense Squad, the alien password was finally cracked. It tells us that in an ancient ruin somewhere on Earth lies a secret weapon to counter this disaster. The squad immediately heads to the site.

Problem Description

To enter the ruin, one must pass a mysterious staircase. You must climb it in the required manner; otherwise, you cannot ascend. The rules are as follows:

1. If the next step’s height exceeds the current step’s height by exactly $1$, you may step onto it directly.

2. Except for the first step, you may retreat from the current step to the previous step.

3. After you have retreated consecutively $k$ times, you may make one jump to any step whose height is at most the current step’s height $+ 2^{k}$. For example, suppose you are now at step $j$, having retreated from step $j + k$. Then you may jump to any step whose height is no more than the current step’s height $+ 2^{k}$. This jump counts as a single move.

You start at step $1$. Due to time pressure, you need to reach the top step using the fewest moves. Please compute the minimum number of moves.

Input Format

• The first line contains an integer $N$, the number of steps.
• The second line contains $N$ integers, the heights of the steps in increasing order.

Output Format

Output a single integer: the minimum number of moves if it is possible to reach the top step; otherwise, output $-1$.

5
0  1  2  3  6 

7

Hint

Sample Explanation: Climb up $3$ steps consecutively, then retreat $3$ steps, and then jump directly to the top.

Constraints:

• For $50\%$ of the testdata, $N \le 20$.
• For $100\%$ of the testdata, $1 \le N \le 200$, and the height of each step does not exceed $2^{31} - 1$.

Translated by ChatGPT 5