Minimum Jumps to Reach the End

In this problem, you are given an array of non-negative integers where each element represents the maximum jump length from that position. Your task is to determine the minimum number of jumps required to reach the last index of the array. If it is not possible to reach the end, return -1.

For example, given the array ( [2, 3, 1, 1, 4] ), you can reach the end in 2 jumps: jump 1 step from index 0 to index 1, then 3 steps to reach the last index. Conversely, an array like ( [0, 1, 1, 1, 1] ) does not allow reaching the end because the first element is 0.

The problem also includes handling multiple test cases. The input begins with an integer ( T ) (the number of test cases). For each test case, the first number indicates ( N ), the size of the array, followed by ( N ) integers representing the maximum jump lengths for each stone.

The greedy approach can be used to solve this problem in an efficient way. At each step, we update the maximum reachable index, and if we exhaust the current step count, we make a jump and update our step counter. The challenge is to determine when it becomes impossible to proceed further.

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( T ) denoting the number of test cases. Each test case starts with an integer ( N ) representing the number of stones, followed by ( N ) space-separated integers where each integer indicates the maximum jump length from that stone.

outputFormat

For each test case, output a single line containing the minimum number of jumps needed to reach the end of the array, or -1 if it is not possible.## sample

6
5 2 3 1 1 4
5 0 1 1 1 1
5 1 0 0 0 0
1 1
3 1 2 3
5 3 2 1 0 4

2
-1
-1
0
2
-1