#include <bits/stdc++.h>
using namespace std;
int n, k, flag[310], ret[310], a[100100], pos[100100], lst[100100], w[100100],
    f[100100], cnt[310][100100];
int mo(int x, int y) { return x + y < 998244353 ? x + y : x + y - 998244353; }
void add(int l, int r, int x) {
  int s = (l - 1) / 350 + 1, t = r / 350 + 1;
  if (s == t) {
    for (int i = l; i <= r; i++) {
      w[i] += x;
      cnt[s][w[i] - x] = mo(cnt[s][w[i] - x], 998244353 - f[i - 1]),
                    cnt[s][w[i]] = mo(cnt[s][w[i]], f[i - 1]);
      if (x == 1 && w[i] == k - flag[s] + 1)
        ret[s] = mo(ret[s], 998244353 - f[i - 1]);
      else if (x == -1 && w[i] == k - flag[s])
        ret[s] = mo(ret[s], f[i - 1]);
    }
    return;
  }
  for (int i = l; i <= s * 350; i++) {
    w[i] += x;
    cnt[s][w[i] - x] = mo(cnt[s][w[i] - x], 998244353 - f[i - 1]),
                  cnt[s][w[i]] = mo(cnt[s][w[i]], f[i - 1]);
    if (x == 1 && w[i] - 1 == k - flag[s])
      ret[s] = mo(ret[s], 998244353 - f[i - 1]);
    else if (x == -1 && w[i] == k - flag[s])
      ret[s] = mo(ret[s], f[i - 1]);
  }
  for (int i = s + 1; i < t; i++) {
    flag[i] += x;
    if (x == 1)
      ret[i] = mo(ret[i], 998244353 - cnt[i][k - flag[i] + 1]);
    else
      ret[i] = mo(ret[i], cnt[i][k - flag[i]]);
  }
  for (int i = (t - 1) * 350 + 1; i <= r; i++) {
    w[i] += x;
    cnt[t][w[i] - x] = mo(cnt[t][w[i] - x], 998244353 - f[i - 1]),
                  cnt[t][w[i]] = mo(cnt[t][w[i]], f[i - 1]);
    if (x == 1 && w[i] - 1 == k - flag[t])
      ret[t] = mo(ret[t], 998244353 - f[i - 1]);
    else if (x == -1 && w[i] == k - flag[t])
      ret[t] = mo(ret[t], f[i - 1]);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) lst[i] = pos[a[i]], pos[a[i]] = i;
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    add(lst[i] + 1, i - 1, 1);
    if (lst[i]) add(lst[lst[i]] + 1, lst[i], -1);
    for (int j = 1; j <= (i - 1) / 350 + 1; j++) f[i] = mo(f[i], ret[j]);
    if (k >= 1)
      f[i] = mo(f[i], f[i - 1]),
      ret[(i - 1) / 350 + 1] = mo(ret[(i - 1) / 350 + 1], f[i - 1]);
    w[i] = 1;
    cnt[(i - 1) / 350 + 1][1] = mo(cnt[(i - 1) / 350 + 1][1], f[i - 1]);
  }
  printf("%d\n", f[n]);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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.

Input

The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 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, …, a_n (1 ≤ a_i ≤ n) — elements of the array a.

Output

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

Examples

Input


3 1
1 1 2


Output


3


Input


5 2
1 1 2 1 3


Output


14


Input


5 5
1 2 3 4 5


Output


16

Note

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].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, flag[310], ret[310], a[100100], pos[100100], lst[100100], w[100100],
    f[100100], cnt[310][100100];
int mo(int x, int y) { return x + y < 998244353 ? x + y : x + y - 998244353; }
void add(int l, int r, int x) {
  int s = (l - 1) / 350 + 1, t = r / 350 + 1;
  if (s == t) {
    for (int i = l; i <= r; i++) {
      w[i] += x;
      cnt[s][w[i] - x] = mo(cnt[s][w[i] - x], 998244353 - f[i - 1]),
                    cnt[s][w[i]] = mo(cnt[s][w[i]], f[i - 1]);
      if (x == 1 && w[i] == k - flag[s] + 1)
        ret[s] = mo(ret[s], 998244353 - f[i - 1]);
      else if (x == -1 && w[i] == k - flag[s])
        ret[s] = mo(ret[s], f[i - 1]);
    }
    return;
  }
  for (int i = l; i <= s * 350; i++) {
    w[i] += x;
    cnt[s][w[i] - x] = mo(cnt[s][w[i] - x], 998244353 - f[i - 1]),
                  cnt[s][w[i]] = mo(cnt[s][w[i]], f[i - 1]);
    if (x == 1 && w[i] - 1 == k - flag[s])
      ret[s] = mo(ret[s], 998244353 - f[i - 1]);
    else if (x == -1 && w[i] == k - flag[s])
      ret[s] = mo(ret[s], f[i - 1]);
  }
  for (int i = s + 1; i < t; i++) {
    flag[i] += x;
    if (x == 1)
      ret[i] = mo(ret[i], 998244353 - cnt[i][k - flag[i] + 1]);
    else
      ret[i] = mo(ret[i], cnt[i][k - flag[i]]);
  }
  for (int i = (t - 1) * 350 + 1; i <= r; i++) {
    w[i] += x;
    cnt[t][w[i] - x] = mo(cnt[t][w[i] - x], 998244353 - f[i - 1]),
                  cnt[t][w[i]] = mo(cnt[t][w[i]], f[i - 1]);
    if (x == 1 && w[i] - 1 == k - flag[t])
      ret[t] = mo(ret[t], 998244353 - f[i - 1]);
    else if (x == -1 && w[i] == k - flag[t])
      ret[t] = mo(ret[t], f[i - 1]);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) lst[i] = pos[a[i]], pos[a[i]] = i;
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    add(lst[i] + 1, i - 1, 1);
    if (lst[i]) add(lst[lst[i]] + 1, lst[i], -1);
    for (int j = 1; j <= (i - 1) / 350 + 1; j++) f[i] = mo(f[i], ret[j]);
    if (k >= 1)
      f[i] = mo(f[i], f[i - 1]),
      ret[(i - 1) / 350 + 1] = mo(ret[(i - 1) / 350 + 1], f[i - 1]);
    w[i] = 1;
    cnt[(i - 1) / 350 + 1][1] = mo(cnt[(i - 1) / 350 + 1][1], f[i - 1]);
  }
  printf("%d\n", f[n]);
}

```