María has a sequence of $$$n$$$ integers $$$a_i$$$. María only likes VonitA sequences, which consist of either an increasing sequence (i.e., $$$a_i \leq a_{i+1}$$$) until a certain point, and then a decreasing sequence (i.e., $$$a_i \geq a_{i+1}$$$), or a decreasing sequence followed by an increasing one.
Formally, they must satisfy one of the following properties:
- There is an integer $$$0 \leq k \lt n$$$ such that if $$$0 \leq i \lt k$$$ then $$$a_i \leq a_{i+1}$$$, and if $$$k \leq i \lt n-1$$$ then $$$a_i \geq a_{i+1}$$$.
- There is an integer $$$0 \leq k \lt n$$$ such that if $$$0 \leq i \lt k$$$ then $$$a_i \geq a_{i+1}$$$, and if $$$k \leq i \lt n-1$$$ then $$$a_i \leq a_{i+1}$$$.
What is the minimum number of elements $$$a_i$$$ that María needs to modify in order for her sequence to be VonitA?
The input begins with an integer $$$t$$$ indicating the number of cases.
Each case begins with an integer $$$n$$$, and the next line contains $$$n$$$ integers $$$a_i$$$.
For each case, output a line with the answer.
$$$1 \leq t \leq 100$$$
$$$1 \leq n \leq 10^5$$$
$$$0 \leq a_i \leq 10^9$$$
11 Points: $$$n \leq 15$$$
15 Points: $$$a_i,n \leq 100$$$
10 Points: $$$n \leq 100$$$
15 Points: $$$a_i,n \leq 1000$$$
10 Points: $$$n \leq 1000$$$
39 Points: No restrictions
3 7 1 2 3 4 3 2 1 8 1 2 1 2 1 2 1 2 6 1 4 3 2 3 4
0 3 1
