题目描述

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

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

如果你最优地执行上述过程，求你能获得的最小惩罚值。

$^\dagger$ 序列 $x$ 是序列 $y$ 的子序列，如果 $x$ 可以通过从 $y$ 中删除若干（可能为零或全部）元素得到。

$^\ddagger$ 一些将数组 $a=[3,1,4,1,5]$ 分成 $(s,t)$ 的合法方式有 $([3,4,1,5],[1])$，$([1,1],[3,4,5])$ 和 $([\,],[3,1,4,1,5])$，而一些不合法的方式有 $([3,4,5],[1])$，$([3,1,4,1],[1,5])$ 和 $([1,3,4],[5,1])$。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。接下来的每组测试用例描述如下。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示你能获得的最小惩罚值。

说明/提示

在第一个测试用例中，一种分割方式是 $s=[2,4,5]$，$t=[1,3]$。惩罚值为 $p(s)+p(t)=2+1=3$。

在第二个测试用例中，一种分割方式是 $s=[8,3,1]$，$t=[2,1,7,4,3]$。惩罚值为 $p(s)+p(t)=0+1=1$。

在第三个测试用例中，一种分割方式是 $s=[\,]$，$t=[3,3,3,3,3]$。惩罚值为 $p(s)+p(t)=0+0=0$。

由 ChatGPT 4.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