CF1919C.Grouping Increases

You are given an array $a$ of size $n$. You will do the following process to calculate your penalty:

1. Split array $a$ into two (possibly empty) subsequences$^\dagger$ $s$ and $t$ such that every element of $a$ is either in $s$ or $t^\ddagger$.
2. For an array $b$ of size $m$, define the penalty $p(b)$ of an array $b$ as the number of indices $i$ between $1$ and $m - 1$ where $b_i \lt b_{i + 1}$.
3. The total penalty you will receive is $p(s) + p(t)$.

If you perform the above process optimally, find the minimum possible penalty you will receive.

$^\dagger$ A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements.

$^\ddagger$ Some valid ways to split array $a=[3,1,4,1,5]$ into $(s,t)$ are $([3,4,1,5],[1])$, $([1,1],[3,4,5])$ and $([\,],[3,1,4,1,5])$ while some invalid ways to split $a$ are $([3,4,5],[1])$, $([3,1,4,1],[1,5])$ and $([1,3,4],[5,1])$.

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

1. 将数组 $a$ 拆分为两个（可能为空的）子序列$^\dagger$ $s$ 和 $t$，使得 $a$ 中的每个元素恰好属于 $s$ 或 $t$ 中的一个$^\ddagger$。
2. 对于大小为 $m$ 的数组 $b$，定义其惩罚值 $p(b)$ 为满足 $1 \le i \le m - 1$ 且 $b_i \lt b_{i + 1}$ 的下标 $i$ 的个数。
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])$。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer representing the minimum possible penalty you will receive.

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

In the first test case, a possible way to split $a$ is $s=[2,4,5]$ and $t=[1,3]$. The penalty is $p(s)+p(t)=2 + 1 =3$.

In the second test case, a possible way to split $a$ is $s=[8,3,1]$ and $t=[2,1,7,4,3]$. The penalty is $p(s)+p(t)=0 + 1 =1$.

In the third test case, a possible way to split $a$ is $s=[\,]$ and $t=[3,3,3,3,3]$. The penalty is $p(s)+p(t)=0 + 0 =0$.

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

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

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