P1929 Mysterious Staircase

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.

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.

- 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 a single integer: the minimum number of moves if it is possible to reach the top step; otherwise, output $-1$.

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