Sort Zero

题意翻译

你将会得到一个正整数 $n$ 与 $n$ 个正整数 $a_1,a_2,...,a_n$。$(1\le n\le10^5,1\le a_i\le n)$ 每一次你可以做以下操作： 1. 选择一个正整数 $x$ 2. 将所有等于 $x$ 的数改为 $0$ 输出满足 $\forall i,a_{i-1}\le a_i$ 的最少操作次数。

题目描述

An array is sorted if it has no inversions A Young Boy You are given an array of $ n $ positive integers $ a_1,a_2,\ldots,a_n $ . In one operation you do the following: 1. Choose any integer $ x $ . 2. For all $ i $ such that $ a_i = x $ , do $ a_i := 0 $ (assign $ 0 $ to $ a_i $ ). Find the minimum number of operations required to sort the array in non-decreasing order.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ). The second line of each test case contains $ n $ positive integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

输入输出样例

输入样例 #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

说明

In the first test case, you can choose $ x = 3 $ for the operation, the resulting array is $ [0, 0, 2] $ . In the second test case, you can choose $ x = 1 $ for the first operation and $ x = 3 $ for the second operation, the resulting array is $ [0, 0, 0, 0] $ .

**题目大意**：

给定一个包含 $ n $ 个正整数的数组 $ a_1, a_2, \ldots, a_n $（$ 1 \le n \le 10^5 $，$ 1 \le a_i \le n $）。每次操作可以选择一个整数 $ x $，并将数组中所有等于 $ x $ 的数改为 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 $。

- **输出格式**：
- 对于每个测试用例，输出一行，包含一个整数，表示将数组排序所需的最少操作次数。

**输入输出样例**：

- 输入样例 #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
```**题目大意**： 给定一个包含 $ n $ 个正整数的数组 $ a_1, a_2, \ldots, a_n $（$ 1 \le n \le 10^5 $，$ 1 \le a_i \le n $）。每次操作可以选择一个整数 $ x $，并将数组中所有等于 $ x $ 的数改为 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 $。 - **输出格式**： - 对于每个测试用例，输出一行，包含一个整数，表示将数组排序所需的最少操作次数。 **输入输出样例**： - 输入样例 #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 ```