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

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
- Ai≥AjAi≥Aj
- for all kk (i<k<ji<k<j), Ak≤AjAk≤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

- 1≤T≤1001≤T≤100
- 2≤N≤1052≤N≤105
- 0≤Ai≤1050≤Ai≤105 for each valid ii
- the sum of NN over all test cases does not exceed 106106

### Subtasks Crossing Blocks solution codechef

**Subtask #1 (30 points):**

- 2≤N≤1,0002≤N≤1,000
- the sum of NN over all test cases does not exceed 5⋅1045⋅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 20→17→15→8→720→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.