問題文

$N$ 匹の猫が一列に並んでいます。$i$ 番目の猫は左から $i$ 番目にいて、背の高さは $H_i$ です。ここで、全ての猫の背の高さは互いに相異なることが保証されています。

あなたは、この猫のうち何匹かを選び背の高さを変えることができます。変更後の猫の背の高さは任意の非負の実数値を取ることができます。

猫の背の高さを変更した後以下の条件を満たすようにしたいとき、最小で何回猫の背を変えればよいかを求めてください。

• ある整数 $(x,y,z)$ が存在し、以下の条件をすべて満たす。
• $1< x< y< z< N$
• $1\leq i< x$ を満たす任意の $i$ について、$H_i> H_{i+1}$
• $x\leq i< y$ を満たす任意の $i$ について、$H_i< H_{i+1}$
• $y\leq i< z$ を満たす任意の $i$ について、$H_i> H_{i+1}$
• $z\leq i< N$ を満たす任意の $i$ について、$H_i< H_{i+1}$

$T$ 個のテストケースが与えられるので、全てについて解を求めてください。

制約

• $1\leq T\leq 4\times 10^4$
• $5\leq N\leq 2\times 10^5$
• $1\leq H_i\leq 10^9\ (1\leq i\leq N)$
• $H_i\neq H_j\ (i\neq j)$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられます。

$N$
$H_1\ H_2\ \ldots\ H_N$

出力

$T$ 行出力してください。

$i$ 行目には、 $i$ 番目のテストケースに対する答を出力してください。

サンプル

2
7
9 3 4 2 7 6 1
9
9342 314 159 256 2718 1024 1414 169 231

2
1