题目描述

Stalin Sort 是一种有趣的排序算法，旨在消除不合适的元素，而不是贪心地对它们进行正确排序，从而将自己时间复杂度变为$\mathcal{O}(n)$。

它是这样进行的：从数组中的第二个元素开始，如果它严格小于前一个元素（忽略那些已经被删除的元素），则删除它。继续遍历数组，直到它按非降序排序。例如，数组$[1, 4, 2, 3, 6, 5, 5, 7, 7]$经过斯大林排序后的结果是$[1, 4, 6, 7, 7]$。

如果您可以通过对数组的任何子数组$^{\text{∗}}$重复应用 Stalin Sort 来使数组以非递增顺序排序，那么我们将这样的数组定义为vulnerable，根据需要可以多次调用。

给定一个含$n$个整数的数组$a$，确定最少需要从数组中删除几个整数，才能让这个数组变得vulnerable。

$^{\text{∗}}$如果数组$a$可以通过由数组$b$从头部和尾部删除几个（可以是零个或者所有）元素获得，那么我们认为数组$a$是数组$b$的子数组。

输入格式

每个测试点由多组数据组成。每个测试点的第一行包含一个整数$t$ ( $1 \le t \le 500$ )，用于表示测试数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ ( $1 \le n \le 2000$ )，用于表示数组的大小。

每个数据的第二行包含$n$个整数$a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ )

保证$n$在所有数据中不超过$2000$.

输出格式

对于每组数据，输出一个整数，用于表示最少需要从数组中删除几个整数，才能使数组变得vulnerable。

说明/提示

在第1个输入输出样例中，最佳答案是删除数字$3$和$9$.然后我们只剩下$a = [6, 4, 2, 5, 2]$.为了使这个数组变得脆弱，我们可以首先对子数组$[4, 2, 5]$应用 Stalin Sort来获得$a = [6, 4, 5, 2]$，然后在子数组$[6, 4, 5]$上应用 Stalin Sort来获得非递增的数组$a = [6, 2]$

在第2个输入输出样例中，数组已经是非递增的了，因此不必删除任何数。

题面翻译来自映月之晴

样例

6
7
3 6 4 9 2 5 2
5
5 4 4 2 2
8
2 2 4 4 6 6 10 10
1
1000
9
6 8 9 10 12 9 7 5 4
7
300000000 600000000 400000000 900000000 200000000 400000000 200000000

2
0
6
0
4
2