#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9, mod = 998244353, maxm = 409;
int n, k, ans;
int a[maxn], cnt[maxn], lst[maxn], fir[maxn], bl[maxm], br[maxm], col[maxn],
    v[maxn], lazy[maxm], f[maxn], sum[maxm][maxn];
inline void Fir() {
  int size(sqrt(n));
  int pieces(ceil(1.0 * n / size));
  for (int i = 1; i <= pieces; ++i) {
    bl[i] = (i - 1) * size + 1;
    br[i] = (i == pieces ? n : i * size);
    for (int j = bl[i]; j <= br[i]; ++j) col[j] = i;
  }
  for (int i = 1; i <= n; ++i) {
    lst[i] = fir[a[i]];
    fir[a[i]] = i;
  }
}
inline void Modify(int l, int r, int val) {
  int lt(col[l]), rt(col[r]);
  if (lt == rt) {
    for (int i = l; i <= r; ++i) {
      if (val == 1) {
        if (v[i] + lazy[lt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[lt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[lt][v[i]] = (sum[lt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[lt][v[i]] = (sum[lt][v[i]] + f[i]) % mod;
    }
  } else {
    for (int i = l; i <= br[lt]; ++i) {
      if (val == 1) {
        if (v[i] + lazy[lt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[lt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[lt][v[i]] = (sum[lt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[lt][v[i]] = (sum[lt][v[i]] + f[i]) % mod;
    }
    for (int i = bl[rt]; i <= r; ++i) {
      if (val == 1) {
        if (v[i] + lazy[rt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[rt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[rt][v[i]] = (sum[rt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[rt][v[i]] = (sum[rt][v[i]] + f[i]) % mod;
    }
    for (int i = lt + 1; i <= rt - 1; ++i) {
      if (val == 1)
        ans = (ans - sum[i][k - lazy[i]] + mod) % mod;
      else
        ans = (ans + sum[i][k + 1 - lazy[i]]) % mod;
      lazy[i] += val;
    }
  }
}
inline void Update(int x) {
  sum[col[x + 1]][v[x + 1]] = (sum[col[x + 1]][v[x + 1]] + f[x + 1]) % mod;
  ans = (ans + f[x + 1]) % mod;
}
inline void Solve() {
  ans = 1;
  f[1] = 1;
  sum[1][0] = 1;
  for (int i = 1; i <= n; ++i) {
    ++cnt[a[i]];
    int p(lst[i]), q(lst[p]);
    if (cnt[a[i]] == 1) {
      Modify(1, i, 1);
    } else if (cnt[a[i]] == 2) {
      Modify(p + 1, i, 1);
      Modify(1, p, -1);
    } else {
      Modify(p + 1, i, 1);
      Modify(q + 1, p, -1);
    }
    f[i + 1] = ans;
    Update(i);
  }
  printf("%d", f[n + 1]);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  Fir();
  Solve();
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

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;
const int maxn = 1e5 + 9, mod = 998244353, maxm = 409;
int n, k, ans;
int a[maxn], cnt[maxn], lst[maxn], fir[maxn], bl[maxm], br[maxm], col[maxn],
    v[maxn], lazy[maxm], f[maxn], sum[maxm][maxn];
inline void Fir() {
  int size(sqrt(n));
  int pieces(ceil(1.0 * n / size));
  for (int i = 1; i <= pieces; ++i) {
    bl[i] = (i - 1) * size + 1;
    br[i] = (i == pieces ? n : i * size);
    for (int j = bl[i]; j <= br[i]; ++j) col[j] = i;
  }
  for (int i = 1; i <= n; ++i) {
    lst[i] = fir[a[i]];
    fir[a[i]] = i;
  }
}
inline void Modify(int l, int r, int val) {
  int lt(col[l]), rt(col[r]);
  if (lt == rt) {
    for (int i = l; i <= r; ++i) {
      if (val == 1) {
        if (v[i] + lazy[lt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[lt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[lt][v[i]] = (sum[lt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[lt][v[i]] = (sum[lt][v[i]] + f[i]) % mod;
    }
  } else {
    for (int i = l; i <= br[lt]; ++i) {
      if (val == 1) {
        if (v[i] + lazy[lt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[lt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[lt][v[i]] = (sum[lt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[lt][v[i]] = (sum[lt][v[i]] + f[i]) % mod;
    }
    for (int i = bl[rt]; i <= r; ++i) {
      if (val == 1) {
        if (v[i] + lazy[rt] == k) ans = (ans - f[i] + mod) % mod;
      } else {
        if (v[i] + lazy[rt] == k + 1) ans = (ans + f[i]) % mod;
      }
      sum[rt][v[i]] = (sum[rt][v[i]] - f[i] + mod) % mod, v[i] += val,
      sum[rt][v[i]] = (sum[rt][v[i]] + f[i]) % mod;
    }
    for (int i = lt + 1; i <= rt - 1; ++i) {
      if (val == 1)
        ans = (ans - sum[i][k - lazy[i]] + mod) % mod;
      else
        ans = (ans + sum[i][k + 1 - lazy[i]]) % mod;
      lazy[i] += val;
    }
  }
}
inline void Update(int x) {
  sum[col[x + 1]][v[x + 1]] = (sum[col[x + 1]][v[x + 1]] + f[x + 1]) % mod;
  ans = (ans + f[x + 1]) % mod;
}
inline void Solve() {
  ans = 1;
  f[1] = 1;
  sum[1][0] = 1;
  for (int i = 1; i <= n; ++i) {
    ++cnt[a[i]];
    int p(lst[i]), q(lst[p]);
    if (cnt[a[i]] == 1) {
      Modify(1, i, 1);
    } else if (cnt[a[i]] == 2) {
      Modify(p + 1, i, 1);
      Modify(1, p, -1);
    } else {
      Modify(p + 1, i, 1);
      Modify(q + 1, p, -1);
    }
    f[i + 1] = ans;
    Update(i);
  }
  printf("%d", f[n + 1]);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  Fir();
  Solve();
  return 0;
}

```