D. Изоляция
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Найдите количество способов разбить массив $$$a$$$ из $$$n$$$ целых чисел на произвольное количество непересекающихся непустых подотрезков так, чтобы для каждого подотрезка существовало не более $$$k$$$ различных чисел, которые встречаются ровно один раз.

Так как ответ может быть очень большим, выведите остаток от деления ответа на $$$998\,244\,353$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$, разделенных пробелами ($$$1 \leq k \leq n \leq 10^5$$$) — количество элементов в массиве $$$a$$$ и ограничение из условия.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива $$$a$$$.

Выходные данные

Первая и единственная строка вывода должна содержать количество способов разбить элементы массива $$$a$$$ по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3 1
1 1 2
Выходные данные
3
Входные данные
5 2
1 1 2 1 3
Выходные данные
14
Входные данные
5 5
1 2 3 4 5
Выходные данные
16
Примечание

В первом примере возможных разбиений три:

  • $$$[[1], [1], [2]]$$$
  • $$$[[1, 1], [2]]$$$
  • $$$[[1, 1, 2]]$$$

Разбиение $$$[[1], [1, 2]]$$$ невозможно, потому что два целых числа встречаются ровно один раз на отрезке $$$[1, 2]$$$.