CF1129D Isolation

Find the number of ways to divide an array $ a $ of $ n $ integers into any number of disjoint non-empty segments so that, in each segment, there exist at most $ k $ distinct integers that appear exactly once. Since the answer can be large, find it modulo $ 998\,244\,353 $ .

The first line contains two space-separated integers $ n $ and $ k $ ( $ 1 \leq k \leq n \leq 10^5 $ ) — the number of elements in the array $ a $ and the restriction from the statement. The following line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — elements of the array $ a $ .

The first and only line contains the number of ways to divide an array $ a $ modulo $ 998\,244\,353 $ .

In the first sample, the three possible divisions are as follows. - $ [[1], [1], [2]] $ - $ [[1, 1], [2]] $ - $ [[1, 1, 2]] $ Division $ [[1], [1, 2]] $ is not possible because two distinct integers appear exactly once in the second segment $ [1, 2] $ .