#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 1e5 + 10, mod = 998244353;
int n, k, a[N], b[N], pos[N], Pos[N], dp[N];
int block, id[N], sum[320][700], Sum[320];
inline void Mod(int &x, int y) { x += y, x = (x >= mod) ? x - mod : x; }
inline void ReBuild(int pos) {
  int l = (pos - 1) * block + 1, r = min(n, pos * block), suf = block;
  for (register int i = (0); i <= (block << 1); i++) sum[pos][i] = 0;
  for (register int i = (r); i >= (l); i--)
    suf += b[i], Mod(sum[pos][suf], dp[i - 1]);
  for (register int i = (1); i <= (block << 1); i++)
    Mod(sum[pos][i], sum[pos][i - 1]);
  Sum[pos] = suf - block;
}
inline int Query(int x) {
  int pos = id[x], l = (pos - 1) * block + 1, suf = 0, ans = 0;
  for (register int i = (x); i >= (l); i--)
    suf += b[i], Mod(ans, (suf <= k) * dp[i - 1]);
  for (register int i = (pos - 1); i >= (1); i--) {
    if (k - suf + block >= 0)
      Mod(ans, sum[i][min(block << 1, k - suf + block)]);
    suf += Sum[i];
  }
  return ans;
}
int main() {
  n = read(), k = read(), block = sqrt(n);
  for (register int i = (1); i <= (n); i++)
    a[i] = read(), id[i] = (i - 1) / block + 1;
  dp[0] = 1;
  for (register int i = (1); i <= (n); i++) {
    b[i] = 1;
    if (pos[a[i]]) {
      if (Pos[a[i]]) b[Pos[a[i]]] = 0, ReBuild(id[Pos[a[i]]]);
      Pos[a[i]] = pos[a[i]], b[pos[a[i]]] = -1, ReBuild(id[pos[a[i]]]);
    }
    pos[a[i]] = i, dp[i] = Query(i);
    if (i != n && id[i + 1] != id[i]) ReBuild(id[i]);
  }
  printf("%d\n", dp[n]);
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
inline long long read() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 1e5 + 10, mod = 998244353;
int n, k, a[N], b[N], pos[N], Pos[N], dp[N];
int block, id[N], sum[320][700], Sum[320];
inline void Mod(int &x, int y) { x += y, x = (x >= mod) ? x - mod : x; }
inline void ReBuild(int pos) {
  int l = (pos - 1) * block + 1, r = min(n, pos * block), suf = block;
  for (register int i = (0); i <= (block << 1); i++) sum[pos][i] = 0;
  for (register int i = (r); i >= (l); i--)
    suf += b[i], Mod(sum[pos][suf], dp[i - 1]);
  for (register int i = (1); i <= (block << 1); i++)
    Mod(sum[pos][i], sum[pos][i - 1]);
  Sum[pos] = suf - block;
}
inline int Query(int x) {
  int pos = id[x], l = (pos - 1) * block + 1, suf = 0, ans = 0;
  for (register int i = (x); i >= (l); i--)
    suf += b[i], Mod(ans, (suf <= k) * dp[i - 1]);
  for (register int i = (pos - 1); i >= (1); i--) {
    if (k - suf + block >= 0)
      Mod(ans, sum[i][min(block << 1, k - suf + block)]);
    suf += Sum[i];
  }
  return ans;
}
int main() {
  n = read(), k = read(), block = sqrt(n);
  for (register int i = (1); i <= (n); i++)
    a[i] = read(), id[i] = (i - 1) / block + 1;
  dp[0] = 1;
  for (register int i = (1); i <= (n); i++) {
    b[i] = 1;
    if (pos[a[i]]) {
      if (Pos[a[i]]) b[Pos[a[i]]] = 0, ReBuild(id[Pos[a[i]]]);
      Pos[a[i]] = pos[a[i]], b[pos[a[i]]] = -1, ReBuild(id[pos[a[i]]]);
    }
    pos[a[i]] = i, dp[i] = Query(i);
    if (i != n && id[i + 1] != id[i]) ReBuild(id[i]);
  }
  printf("%d\n", dp[n]);
}

```