Stepping stones are laid in a line, numbered 0 to n − 1. From stone i you can hop forward to any stone up to a[i] positions ahead. You start on stone 0.
Print the fewest hops needed to reach stone n − 1, or -1 if it cannot be reached.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ a[i] ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: a[0..n−1].
- Output
- One integer.
Examples
Input 1
5
2 3 1 1 4Output
2Hop from stone 0 to stone 1 (1 step), then 3 steps to the last stone: 2 hops.
Input 2
5
3 2 1 0 4Output
-1Every route lands on the stone with 0 and gets stuck: -1.
Show hints
- Think of BFS levels: all stones reachable in exactly h hops form a contiguous range.
- Track the end of the current range and the farthest stone reachable from inside it.
Show the explanation
The stones reachable with h hops form a contiguous window, so a greedy scan can play the role of BFS. Walk left to right keeping end (the last stone reachable with the current number of hops) and far (the farthest stone reachable with one more hop). When i reaches end and the goal is not yet covered, take a hop: hops += 1, end = far. If at some point i passes far, the rest is unreachable. Each stone is looked at once.
Original UniCircle question. Last reviewed 22 Oct 2026.