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.

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.

Simons and Beating Peaks

Examples