题目描述

如果一个数组没有逆序对，则称其为有序数组。

一个小男孩

给定一个长度为 $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 翻译

样例

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

1
2
4
3
0