Contents

• For Solution

Bob gave him a sequence of blocks with heights A1,A2,,ANA1,A2,…,AN. Chef is at the first block and he has to reach the NN-th block using the minimum number of moves to complete the task.

In one move, he can jump from the ii-th block to the jj-th block only if the following conditions are satisfied:

• i<ji<j Crossing Blocks solution codechef
• AiAjAi≥Aj
• for all kk (i<k<ji<k<j), AkAjAk≤Aj

You have to find the minimum number of moves Chef needs to perform to reach the last block, or determine that it is impossible.

Input Format Crossing Blocks solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the minimum number of moves or 1−1 if it is impossible to reach the last block.

Constraints

• 1T1001≤T≤100
• 2N1052≤N≤105
• 0Ai1050≤Ai≤105 for each valid ii
• the sum of NN over all test cases does not exceed 106106

• 2N1,0002≤N≤1,000
• the sum of NN over all test cases does not exceed 51045⋅104

Subtask #2 (70 points): original constraints

Sample Input 1

2
5
9 15 8 13 8
9
20 16 13 9 17 11 15 8 7


Sample Output 1  Crossing Blocks solution codechef

-1
4


Explanation

Example case 1: There is no way to move from the first block (with height 99) to any other block.

Example case 2: The only sequence of 44 moves is 2017158720→17→15→8→7. For example, in the first move, all the heights between 2020 and 1717 do not exceed 1717, so all conditions are satisfied.