Minimum Number Of Taps To Water Garden

The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

Example :

Follow Up:

Can you solve the problem in O(N) time?

Input Format:

The first line contains a single integer T representing the number of test cases. 

The first line of each test case will contain the integer N.

The second and the last line of each test case will contain N single space-separated integers representing the elements of the array “ranges”.

Output format :

For each test case, print a single integer representing the value of the minimum number of taps needed to open by the gardener to fill the whole garden.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
0 <= ranges[i] <= 100

Time Limit: 1 sec