← 返回题目列表

Codeforces · 1712/C

C. 排序零

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

给定一个由 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ 组成的数组。

在一项操作中,您将执行以下操作:

1. 选择任意整数$$$x$$$。
2. 对于所有 $$$i$$$,使得 $$$a_i = x$$$,执行 $$$a_i := 0$$$ (将 $$$0$$$ 分配给 $$$a_i$$$)。

查找以非降序对数组进行排序所需的最少操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 以非递减顺序对数组进行排序所需的最少操作数。

示例

输入 #1

5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1

输出 #1

1
2
4
3
0

注意

第一个测试用例中,可以选择$$$x = 3$$$进行运算,得到的数组为$$$[0, 0, 2]$$$。

在第二个测试用例中,第一次操作可以选择 $$$x = 1$$$,第二次操作可以选择 $$$x = 3$$$,结果数组为 $$$[0, 0, 0, 0]$$$。