Единственное отличие между простой и сложной версиями — ограничения.
Канал 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\) целых чисел — ответы на заданные наборы входных данных в порядке их следования в тесте. Ответом на набор входных данных является минимальное количество сериалов, подписку на которые надо приобрести, чтобы была возможность \(d\) дней подряд смотреть по BerTV эпизодов приобретённого сериала. Обратите внимание, что допустимо, что у будет возможность посмотреть более \(d\) дней подряд.
Примечание
В первом наборе входных данных примера чтобы была возможность смотреть два дня подряд сериалы, обязательно нужно купить подписку и на сериал \(1\), и на сериал \(2\). Таким образом, ответ равен двум.
Во втором наборе входных данных примера можно купить подписку на любой из трёх сериалов, так как для каждого сериала есть отрезок из трех подряд дней, состоящий только из эпизодов этого сериала.
В третьем наборе входных данных примера в единственном отрезке из четырех дней встречаются четыре разных сериала, поэтому нужно приобрести подписку на все эти четыре сериала.
В четвертом наборе входных данных примера можно купить подписки на сериалы \(3,5,7,8,9\), таким образом можно будет смотреть сериалы в течении последних восьми дней.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
2
1
4
5
|