题目内容

在一项地质研究中，记录了某地区 $n$ 个等间距观测点的海拔高度 $h_1, h_2, \dots, h_n$。研究人员定义：如果存在两个观测点 $p < q$ 且 $h_p > h_q$，则称 $(p, q)$ 是一个 异常对。

现在预测会发生一次地壳运动。你可以选择一条断裂带位置 $i$（$1 \le i < n$）和一个整数沉降量 $x$，使得左侧（即 $1$ 到 $i$ 号观测点）整体下沉 $x$ 单位，同时右侧（$i+1$ 到 $n$ 号观测点）整体抬升 $x$ 单位。你也可以不做任何操作。

由于左右两侧的内部相对高度差不会改变，因此各自区域内的异常对个数保持不变。而对于跨越断裂带的点对，总存在足够大的 $x$ 使得所有跨越异常对完全消失。因此，操作结束后，整个序列的异常对数量最小值等于某个分割 $i$ 下，左侧内部异常对数量与右侧内部异常对数量之和的最小值。

请你求出这个最小可能值。

约束：总测试组数 $t$ 不超过 $10^4$，所有测试数据的 $n$ 之和不超过 $2 \times 10^5$，每个海拔高度均为 $1$ 到 $n$ 之间的整数。若 $n = 1$，异常对数量为 $0$。

输入描述

第一行输入一个整数 $t$，表示测试数据组数。接下来依次给出每组数据：

• 第一行一个整数 $n$，表示观测点数量。
• 第二行 $n$ 个整数 $h_1, h_2, \dots, h_n$，表示各观测点的初始海拔高度。

保证 $t \le 10^4$，$1 \le n \le 2 \times 10^5$，且所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$，每个 $h_i$ 满足 $1 \le h_i \le n$。

输出描述

对于每组测试数据，输出一行一个整数，表示经过至多一次地壳运动后序列中异常对数量的最小值。

样例1

输入

1
1
1

输出

0

说明

n=1 时无法选择满足条件的 i，无法进行操作，因此最多可进行的操作次数为 0。

样例2

输入

1
5
3 2 1 5 4

输出

1

说明

n=5>1，可以选择一个 i 进行一次操作，因此最多可进行的操作次数为 1。

样例3

输入

2
2
2 1
4
2 4 1 3

输出

1
1

说明

第一组数据 n=2>1，可进行操作，最多操作次数为 1；第二组 n=4>1，同样可进行操作，最多操作次数为 1。