CF1367F2 Flying Sort (Hard Version)

这是该问题的困难版本。在本版本中，给定的数组可以包含相等的元素，并且 $n$ 的约束比简单版本更大。 给定一个长度为 $n$ 的整数数组 $a$（该数组可以包含相等的元素）。你可以对数组元素进行以下操作： 1. 选择任意下标 $i$（$1 \le i \le n$），将元素 $a[i]$ 移动到数组的开头； 2. 选择任意下标 $i$（$1 \le i \le n$），将元素 $a[i]$ 移动到数组的末尾。 例如，如果 $n = 5$，$a = [4, 7, 2, 2, 9]$，那么可以进行如下操作序列： - 对第二个元素执行第一种操作后，数组 $a$ 变为 $[7, 4, 2, 2, 9]$； - 对第二个元素执行第二种操作后，数组 $a$ 变为 $[7, 2, 2, 9, 4]$。 你可以以任意顺序、任意次数地执行任意类型的操作。 请你求出，使数组 $a$ 变为非递减有序（即满足 $a[1] \le a[2] \le \ldots \le a[n]$）所需的最少操作次数（第一种和第二种操作的总次数）。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示需要通过上述操作排序的数组。给定的数组可以包含相等的元素。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个测试用例中，你需要先将两个 $2$ 移动到数组开头。因此，期望的操作序列为：$[4, 7, 2, 2, 9] \rightarrow [2, 4, 7, 2, 9] \rightarrow [2, 2, 4, 7, 9]$。 在第二个测试用例中，你需要将 $1$ 移动到数组开头，将 $8$ 移动到数组末尾。因此，期望的操作序列为：$[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$。 在第三个测试用例中，数组已经是有序的。 由 ChatGPT 4.1 翻译