← 返回题目列表

Codeforces · 1367/F2

F2. 飞行排序(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,给定数组可以包含相等的元素,并且对 $$$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$$$。

输出

对于每个测试用例输出一个整数——第一类和第二类操作的最小总数,这将使数组按非降序排序。

示例

输入 #1

9
5
4 7 2 2 9
5
3 5 8 1 7
5
1 2 2 4 5
2
0 1
3
0 1 0
4
0 1 0 0
4
0 1 0 1
4
0 1 0 2
20
16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9

输出 #1

2
2
0
0
1
1
1
1
16

注意

在第一个测试用例中,您首先需要将两个 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]$$$。

在第三个测试用例中,数组已经排序。