Minimum Jumps to Reach the End

You are given a sequence of integers representing the maximum jump length from that rung. Starting at the first rung, your task is to compute the minimum number of jumps required to reach the last rung in the sequence. If it is not possible to reach the last rung, output -1.

The jumping rules are as follows:

• If there is only one rung, no jumps are required.
• If the value at the first rung is 0 and there is more than one rung, it is impossible to proceed.
• At each rung, you can jump to any of the next rungs up to the maximum distance allowed by the current rung's value.

Solve the problem using an optimal (greedy) approach.

Note: All formulas referenced in this statement, such as the update rule for the maximum reachable index, are expressed in LaTeX format when needed: for example, the update is given by \(maxReach = \max(maxReach, i + rungs[i])\).

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a single integer \(n\), indicating the number of rungs.
2. The second line contains \(n\) space-separated integers which represent the jump capacity at each rung.

outputFormat

The output is a single integer printed to stdout, representing the minimum number of jumps required to reach the last rung. If the last rung cannot be reached, output -1.

1
0

0