说明

时间限制：1 Sec 内存限制：256 MB 输入文件：punish.in 输出文件：punish.out

给定一个大小为 $n$ 的数组 $a$。你需要按照以下过程计算惩罚值：

1. 将数组 $a$ 分成两个（可能为空）子序列 $s$ 和 $t$，使得 $a$ 的每个元素要么属于 $s$，要么属于 $t$。
2. 对于一个大小为 $m$ 的数组 $b$，定义数组 $b$ 的惩罚值 $p(b)$ 为满足 $b_i < b_{i+1}$ 的下标 $i$（$1 \le i \lt m$）的数量。
3. 最终获得的总惩罚值为 $p(s) + p(t)$。

可以用你喜欢的任何策略执行上述过程，求能获得的最小惩罚值。

注：如果从序列 $y$ 里删除若干个元素（可以是零个或全部）得到序列 $x$，则称 $x$ 是 $y$ 的子序列。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组询问，每组询问包含两行：

第一行为一个整数 $n$；

第二行为空格分隔的 $n$ 个整数 $a_1$、$a_2$、……、$a_n$。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数，表示能获得的最小惩罚值。

样例

样例 1

5
5
1 2 3 4 5
8
8 2 3 1 1 7 4 3
5
3 3 3 3 3
1
1
2
2 1

3
1
0
0
0

样例说明：

在第 $1$ 组询问中，一种分割方式是 $s=[2,4,5]$，$t=[1,3]$。惩罚值为 $p(s)+p(t)=2+1=3$；

在第 $2$ 组询问中，一种分割方式是 $s=[8,3,1]$，$t=[2,1,7,4,3]$。惩罚值为 $p(s)+p(t)=0+1=1$；

在第 $3$ 组询问中，一种分割方式是 $s=[\,]$，$t=[3,3,3,3,3]$。惩罚值为 $p(s)+p(t)=0+0=0$。

数据范围

$1 \le t \le 10^4$

$1\le n\le 2 \times 10^5$

$1 \le a_i \le n$