CF2027B Stalin Sort

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个输入输出样例中，数组已经是非递增的了，因此不必删除任何数。 题面翻译来自[映月之晴](https://www.luogu.com.cn/user/505433)