D. Simons and Beating Peaks
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

My loveliest wishes dissolved into the air; At eighteen, I poured my dreams into the mic to share.
— SHUN, 720

We call an array $$$b$$$ of length $$$m$$$ cool if and only if:

  • There exists no index $$$i$$$ ($$$1 \lt i \lt m$$$) such that $$$b_i=\max(\{b_{i-1}, b_i, b_{i+1}\})$$$.

Simons has an array $$$a$$$ of size $$$n$$$. Initially, the array is a permutation$$$^{\text{∗}}$$$.

He must perform the following operation until the array is cool:

  • Choose an index $$$i$$$ ($$$1 \lt i \lt n$$$) such that $$$a_i=\max(\{a_{i-1}, a_i, a_{i+1}\})$$$.
  • Then, he can remove either $$$a_{i-1}$$$ or $$$a_{i+1}$$$ from the array. After removal, a gap appears in the array, and the left and right sides of the gap will be rejoined.

Find the minimum number of operations for Simons to perform.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$). The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$3\le n\le 5\cdot 10^5$$$) — the size of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$, all $$$a_i$$$-s are distinct) — the array Simons has initially.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of operations for Simons to perform.

Example
Input
5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6
Output
0
1
3
3
9
Note

In the first test case, the array is cool initially, so Simons can't perform any operation. The answer is $$$0$$$.

In the second test case, Simons can perform as follows:

  • Choose index $$$3$$$, because $$$a_3=\max(\{a_2,a_3,a_4\})$$$. Then, he removes $$$a_{2}$$$ from the array. The array becomes $$$[4,3,2,5]$$$.

We can see the array is cool now. Thus, the answer is $$$1$$$.

In the third test case, Simons can perform as follows:

  • Choose index $$$2$$$. Then, he removes $$$a_1$$$ from the array. The array becomes $$$[5,3,6,2,1]$$$.
  • Choose index $$$3$$$. Then, he removes $$$a_2$$$ from the array. The array becomes $$$[5,6,2,1]$$$.
  • Choose index $$$2$$$. Then, he removes $$$a_1$$$ from the array. The array becomes $$$[6,2,1]$$$.

Thus, Simons makes the array cool in $$$3$$$ operations.