Minimum Jumps to Reach the End

You are given an array of non-negative integers arr 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 end of the array (i.e. the last index). If it is impossible to reach the end, return -1.

Formally, if we denote the array length by \(n\) and the array elements by \(a_0, a_1, \dots, a_{n-1}\), you must find the minimum number of jumps to go from index 0 to index \(n-1\), where a jump from index \(i\) can move to any index \(j\) satisfying \(i < j \le i + a_i\). If no such sequence of jumps exists, output -1.

Note: If the array has only one element, you are already at the destination, so the minimum number of jumps is 0.

The problem can be approached with a greedy algorithm that uses three variables to track the farthest point reachable and the current range of the jump. The key idea is to iterate through the array and update the farthest reachable index. Once you pass the current reachable range, it indicates a jump is necessary.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1
arr1[0] arr1[1] ... arr1[N1-1]
N2
arr2[0] arr2[1] ... arr2[N2-1]
...
NT
arrT[0] arrT[1] ... arrT[NT-1]

where:

• T is an integer representing the number of test cases.
• For each test case, the first line contains an integer N which is the number of elements in the array, followed by a line with N space-separated non-negative integers representing the array elements.

outputFormat

For each test case, output on a separate line a single integer representing the minimum number of jumps required to reach the last index of the array, or -1 if it is not possible.

The output should be written to standard output (stdout).

## sample

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

2
-1
0

</p>