D. Mismatched Material
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sengoku Nadeko has been given an array $$$a$$$ of $$$n$$$ values. Please help her find the minimum number of element modifications needed to make to $$$a$$$ such that it is possible to construct an array $$$b$$$ of $$$n+1$$$ values that satisfies $$$a_i = max(b_i, b_{i+1})$$$ for all $$$i$$$ from $$$0$$$ to $$$n-1$$$.

Input

Sengoku Nadeko actually has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases to solve.

The first line of each test case will contain a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$). The next line will contain n integers where the $$$i$$$-th integer is $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2\cdot10^5$$$.

Output

For each test case, output the minimum number of elements that need to be modified in $$$a$$$ such that there exists an array $$$b$$$ that satisfies the conditions in the problem statement.

Example
Input
1
4
2 4 6 3
Output
1
Note

In the example, modifying $$$a_4$$$ from $$$3$$$ to be $$$8$$$ makes $$$a=[2, 4, 6, 8]$$$, so a possible $$$b$$$ could be $$$b=[2, 1, 4, 6, 8]$$$.

Problem Credits: Eric Yachbes