CF1223D Sequence Sorting

给定一个整数序列 $a_1, a_2, \dots, a_n$。 你可以对该序列进行如下操作：选择某个整数 $x$，将所有等于 $x$ 的元素一起移动到序列的开头或结尾。注意，每次操作必须将所有等于 $x$ 的元素统一移动到一个方向。 例如，若 $a = [2, 1, 3, 1, 1, 3, 2]$，你可以通过一次操作得到以下序列（为方便起见，将等于 $x$ 的元素称为 $x$ 元素）： - 若将所有 $1$ 元素移到开头，得到 $[1, 1, 1, 2, 3, 3, 2]$； - 若将所有 $1$ 元素移到结尾，得到 $[2, 3, 3, 2, 1, 1, 1]$； - 若将所有 $2$ 元素移到开头，得到 $[2, 2, 1, 3, 1, 1, 3]$； - 若将所有 $2$ 元素移到结尾，得到 $[1, 3, 1, 1, 3, 2, 2]$； - 若将所有 $3$ 元素移到开头，得到 $[3, 3, 2, 1, 1, 1, 2]$； - 若将所有 $3$ 元素移到结尾，得到 $[2, 1, 1, 1, 2, 3, 3]$。 你需要求出，使序列 $a$ 变为非降序（即对于所有 $2 \le i \le n$，都有 $a_{i-1} \le a_i$）所需的最少操作次数。 注意，你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$），表示询问的数量。每个询问由两行组成。 每个询问的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示序列的长度。 每个询问的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示序列的元素。 保证所有 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个询问，输出一个整数，表示将序列 $a$ 排成非降序所需的最少操作次数。

对于第一个询问，你可以先将所有 $1$ 元素移到开头（此时序列变为 $[1, 1, 1, 3, 6, 6, 3]$），再将所有 $6$ 元素移到结尾。 对于第二个询问，序列本身已经有序，因此答案为 $0$。 对于第三个询问，你需要将所有 $2$ 元素移到开头。 由 ChatGPT 4.1 翻译