CF1712C.Sort Zero

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.

如果一个数组没有逆序对，则称该数组是已排序的。

一个小男孩

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

每次操作你可以执行以下步骤：

1. 任选一个整数 $x$；
2. 对所有满足 $a_i = x$ 的下标 $i$，令 $a_i := 0$（即将 $a_i$ 赋值为 $0$）。

求使该数组变为非递减顺序所需的最少操作次数。

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$.

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

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

对于每个测试用例，输出一个整数——将数组按非递减顺序排序所需的最少操作次数。

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]$.

在第一个测试用例中，你可以选择 $x = 3$ 执行该操作，得到的数组为 $[0, 0, 2]$。

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