Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef is very adventurous, so he asked Bob to give him a task.

Bob gave him a sequence of blocks with heights $A_{1}, A_{2}, \ldots, A_{N}.$ Chef is at the first block and he has to reach the N-th block using the minimum number of moves to complete the task.

In one move, he can jump from the i-th block to the j-th block only if the following conditions are satisfied:
i < j
A_{i} ≥ A_{j}
for all k (i < k < j), A_{k} ≤ A_{j}

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 ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

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

------ Constraints ------

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{5}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^{6}$

------ subtasks ------

Subtask #1 (30 points):
$2 ≤ N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{4}$

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 ------
-1
4
----- explanation 1 ------
Example case 1: There is no way to move from the first block (with height $9$) to any other block.

Example case 2: The only sequence of $4$ moves is $20 \rightarrow 17 \rightarrow 15 \rightarrow 8 \rightarrow 7$. For example, in the first move, all the heights between $20$ and $17$ do not exceed $17$, so all conditions are satisfied.

见题面

见题面