这是问题的困难版本。版本之间的差异在于,在这个版本中,$$$n\le 4\cdot 10^5$$$。只有解决了该问题的所有版本,您才能破解。
Serval 有一个神奇的数字 $$$k$$$ ($$$k\ge 2$$$)。我们称数组为$$$r$$$ 多彩 当且仅当:
- $$$r$$$ 的长度为 $$$k$$$,并且
- $$$1$$$ 和 $$$k$$$ 之间的每个整数出现 正好一次 在$$$r$$$。
给定一个数组 $$$a$$$,由 $$$1$$$ 和 $$$k$$$ 之间的 $$$n$$$ 整数组成。保证 $$$1$$$ 和 $$$k$$$ 之间的每个整数在 $$$a$$$ 中至少出现一次。您可以对$$$a$$$执行以下操作:
- 选择一个索引 $$$i$$$ ($$$1\le i \lt n$$$),然后交换 $$$a_i$$$ 和 $$$a_{i+1}$$$。
求至少生成一个 $$$a$$$ 子数组$$$^{\text{∗}}$$$ 所需的最少操作数 多彩。可以证明,在问题的约束下这总是可能的。
$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\leq k\leq n\leq 4\cdot 10^5$$$) — 数组 $$$a$$$ 的长度和 Serval 的幻数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq k$$$) — 数组 $$$a$$$ 的元素。保证 $$$1$$$ 和 $$$k$$$ 之间的每个整数在 $$$a$$$ 中至少出现一次。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 生成至少一个 $$$a$$$ 子数组所需的最少操作数 多彩.
示例
输入复制
63 21 2 17 32 1 1 3 1 1 26 31 1 2 2 2 36 31 2 2 2 2 310 55 1 3 1 1 2 2 4 1 39 41 2 3 3 3 3 3 2 4
输出复制
0 1 2 3 4 5
注意
在第一个测试用例中,由于子数组 $$$[a_1, a_2] = [1, 2]$$$ 和 $$$[a_2, a_3] = [2, 1]$$$ 已经 多彩,我们不需要执行任何操作。因此,答案是$$$0$$$。
在第二个测试用例中,我们可以交换 $$$a_1$$$ 和 $$$a_2$$$ 得到 $$$[1, \underline{2, 1, 3}, 1, 1, 2]$$$,它有一个 多彩 子数组 $$$[a_2, a_3, a_4] = [2, 1, 3]$$$。并且给定的数组最初没有任何 多彩 子数组,所以答案是 $$$1$$$。