斯大林排序是一种幽默的排序算法,旨在消除不合适的元素,而不是费心对它们进行正确排序,从而提高了 $$$\mathcal{O}(n)$$$ 时间复杂度。
流程如下:从数组中的第二个元素开始,如果它严格小于前一个元素(忽略已经删除的元素),则将其删除。继续迭代数组,直到按非降序排序。例如,数组 $$$[1, 4, 2, 3, 6, 5, 5, 7, 7]$$$ 经过斯大林排序后变成 $$$[1, 4, 6, 7, 7]$$$。
如果您可以通过将斯大林排序重复应用于其任何子数组$$$^{\text{*}}$$$(根据需要多次),以非递增顺序对数组进行排序,我们将数组定义为易受攻击的数组。
给定一个包含 $$$n$$$ 整数的数组 $$$a$$$,确定必须从该数组中删除以使其易受攻击的最小整数数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 必须从数组中删除以使其容易受到攻击的最小整数数。
示例
输入 #1
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
输出 #1
2 0 6 0 4 2
注意
在第一个测试用例中,最佳答案是删除数字 $$$3$$$ 和 $$$9$$$。然后我们剩下 $$$a = [6, 4, 2, 5, 2]$$$。为了证明这个数组是脆弱的,我们可以首先对子数组 $$$[4, 2, 5]$$$ 进行斯大林排序,得到 $$$a = [6, 4, 5, 2]$$$,然后对子数组 $$$[6, 4, 5]$$$ 进行斯大林排序,得到 $$$a = [6, 2]$$$,这是非增的。
在第二个测试用例中,数组已经是非递增的,因此我们不必删除任何整数。