Statement : D. Simons and Beating Peaks

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

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

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

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.