CF1712C Sort Zero

如果一个数组没有逆序对，则称其为有序数组。 一个小男孩 给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \ldots, a_n$。 你可以进行如下操作： 1. 选择任意一个整数 $x$。 2. 对所有满足 $a_i = x$ 的 $i$，将 $a_i$ 赋值为 $0$（即 $a_i := 0$）。 请你求出将数组变为非递减有序所需的最少操作次数。

每组测试数据包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示将数组变为非递减有序所需的最少操作次数。

在第一个测试用例中，你可以选择 $x = 3$ 进行操作，操作后数组变为 $[0, 0, 2]$。 在第二个测试用例中，你可以先选择 $x = 1$，再选择 $x = 3$，操作后数组变为 $[0, 0, 0, 0]$。 由 ChatGPT 4.1 翻译