← 返回题目列表

Codeforces · 2027/B

B. 斯大林排序

中文机器翻译题面 查看原题

斯大林排序是一种幽默的排序算法,旨在消除不合适的元素,而不是费心对它们进行正确排序,从而提高了 $$$\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]$$$,这是非增的。

在第二个测试用例中,数组已经是非递增的,因此我们不必删除任何整数。