← 返回题目列表

Codeforces · 1225/B2

B2. 电视订阅(硬版)

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

简单版本和困难版本之间的唯一区别是限制。

BerTV 频道每天播放 $$$k$$$ 电视节目之一的一集。您知道接下来 $$$n$$$ 天的时间表:整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$),其中 $$$a_i$$$ 是节目,其剧集将在第 $$$i$$$ 天播放。

节目的订阅是针对整个节目(即所有剧集)购买的,对于每个节目,订阅是单独购买的。

您需要至少购买多少订阅才能有机会连续观看 $$$d$$$ ($$$1 \le d \le n$$$) 天购买的节目剧集?换句话说,您希望购买最少数量的电视节目,以便有连续 $$$d$$$ 天的某个片段,其中所有剧集都属于所购买的节目。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例描述。

每个测试用例的第一行包含三个整数 $$$n、k$$$ 和 $$$d$$$ ($$$1 \le n \le 2\cdot10^5$$$、$$$1 \le k \le 10^6$$$、$$$1 \le d \le n$$$)。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 天播出的节目。

保证输入中所有测试用例的$$$n$$$的值之和不超过$$$2\cdot10^5$$$。

输出

打印 $$$t$$$ 整数 — 按其遵循的顺序输入输入中测试用例的答案。测试用例的答案是您需要购买订阅的电视节目的最低数量,以便您可以在 BerTV 上连续 $$$d$$$ 观看购买的电视节目的剧集。请注意,您可以连续观看超过 $$$d$$$ 天。

示例

输入 #1

4
5 2 2
1 2 1 2 1
9 3 3
3 3 3 2 2 2 1 1 1
4 10 4
10 8 6 4
16 9 8
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3

输出 #1

2
1
4
5

注意

在第一个有机会连续两天观看节目的测试用例中,您需要购买节目 $$$1$$$ 和节目 $$$2$$$ 的订阅。所以答案是两个。

在第二个测试用例中,您可以购买任何节目的订阅,因为对于每个节目,您都可以找到连续三天的片段,仅包含该节目的剧集。

在四天的独特片段中的第三个测试用例中,您有四个不同的节目,因此您需要购买所有这四个节目的订阅。

在第四个测试用例中,您可以购买节目 $$$3,5,7,8,9$$$ 的订阅,并且您将能够观看过去八天的节目。