3

NINJA'S JUMP

Difficulty: HARD
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

Input Format:

``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘arr’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.
``````

Output Format:

``````For each test case, print a single line containing the number of starting indices, from where Ninja can reach the end by following the required jump conditions.

The output of each test case will be printed in a separate line.
``````

Note :

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

Constraints:

``````1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6

Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘arr[i]’ represents the elements of the array.

Time Limit: 1 sec
``````

Sample Input 1:

``````2
5
20 23 22 24 25
5
5 6 4 4 7
``````

Sample Output 1:

``````2
3
``````

Explanation for sample input 1:

``````Test Case 1:
For the first test case, if we start from index i = 0, we can make our first jump to i = 2, since it is smaller than all other array values but then we cannot jump anymore.
If we start from the index i = 1, or i = 2 we can make the first jump to i = 3 then we cannot jump anymore.
If we start from index i = 3 we have to make only one jump and we reach the end.
And if we start from index i = 4 we are already at the end.
So we return ‘2’ as our answer as there are ‘2’ good starting index.

Test Case 2:
For the test case if we start From starting index i = 0, we make jumps to i = 1, i = 2, i = 3
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.

In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some number of jumps so we return ‘3’ as our answer.
``````

Sample Input 2:

``````1
5
5 1 3 4 2
``````

Sample Output 2:

``````3
``````

Explanation of sample input 2:

``````As we can reach the end by starting from index 1, 2, 4
``````
Console