B2. Покупка подписок на сериалы (усложнённая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — ограничения.

Канал 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$$$ целых чисел — ответы на заданные наборы входных данных в порядке их следования в тесте. Ответом на набор входных данных является минимальное количество сериалов, подписку на которые надо приобрести, чтобы была возможность $$$d$$$ дней подряд смотреть по BerTV эпизодов приобретённого сериала. Обратите внимание, что допустимо, что у будет возможность посмотреть более $$$d$$$ дней подряд.

Пример
Входные данные
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
Выходные данные
2
1
4
5
Примечание

В первом наборе входных данных примера чтобы была возможность смотреть два дня подряд сериалы, обязательно нужно купить подписку и на сериал $$$1$$$, и на сериал $$$2$$$. Таким образом, ответ равен двум.

Во втором наборе входных данных примера можно купить подписку на любой из трёх сериалов, так как для каждого сериала есть отрезок из трех подряд дней, состоящий только из эпизодов этого сериала.

В третьем наборе входных данных примера в единственном отрезке из четырех дней встречаются четыре разных сериала, поэтому нужно приобрести подписку на все эти четыре сериала.

В четвертом наборе входных данных примера можно купить подписки на сериалы $$$3,5,7,8,9$$$, таким образом можно будет смотреть сериалы в течении последних восьми дней.