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