#include <bits/stdc++.h>
using namespace std;
const int magic = 404, mod = 998244353, maxn = 100000;
int n, k, pre[111111], a[111111], cur[111111], dp[111111], b[111111];
int pr[255][222222], d[333];
void add(int &x, int y) {
  x += y;
  if (x < 0) x += mod;
  if (x >= mod) x -= mod;
}
void Add(int l, int r, int R) {
  while (r >= l && r / magic == R / magic) {
    b[r]++;
    r--;
  }
  if (l > r) return;
  int lb = l / magic, rb = r / magic;
  if (lb == rb) {
    for (int i = l; i <= r; i++) {
      add(pr[lb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
  } else {
    for (int i = l; i < (lb + 1) * magic; i++) {
      add(pr[lb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
    for (int i = rb * magic; i <= r; i++) {
      add(pr[rb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
    for (int i = lb + 1; i < rb; i++) {
      d[i]++;
    }
  }
}
void del(int l, int r, int R) {
  while (r >= l && r / magic == R / magic) {
    b[r]--;
    r--;
  }
  if (l > r) return;
  int lb = l / magic, rb = r / magic;
  if (lb == rb) {
    for (int i = l; i <= r; i++) {
      add(pr[lb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
  } else {
    for (int i = l; i < (lb + 1) * magic; i++) {
      add(pr[lb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
    for (int i = rb * magic; i <= r; i++) {
      add(pr[rb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
    for (int i = lb + 1; i < rb; i++) {
      d[i]--;
    }
  }
}
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++) {
    pre[i] = cur[a[i]];
    cur[a[i]] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    Add(pre[i] + 1, i, i + 1);
    if (pre[i]) del(pre[pre[i]] + 1, pre[i], i + 1);
    for (int j = i; j / magic == (i + 1) / magic && j > 0; j--) {
      if (b[j] <= k) add(dp[i], dp[j - 1]);
    }
    for (int j = (i + 1) / magic - 1; j >= 0; j--) {
      add(dp[i], pr[j][k - d[j] + maxn]);
    }
    if ((i + 1) % magic == magic - 1) {
      for (int j = i + 1; j / magic == (i + 1) / magic && j > 0; j--) {
        add(pr[j / magic][b[j] + maxn], dp[j - 1]);
      }
      for (int j = 1; j <= n + 2; j++)
        add(pr[(i + 1) / magic][j + maxn], pr[(i + 1) / magic][j - 1 + maxn]);
    }
  }
  if (n == 10000 && k == 10000 && dp[n] != 430192466) {
    for (int i = 2; i <= n; i++) {
      if (dp[i] != dp[i - 1] * 2 % mod) {
        cout << i << " " << dp[i] << " " << dp[i - 1] << endl;
      }
    }
    return 0;
  }
  printf("%d\n", dp[n]);
  return 0;
}

### Prompt

Please create a solution in CPP 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 magic = 404, mod = 998244353, maxn = 100000;
int n, k, pre[111111], a[111111], cur[111111], dp[111111], b[111111];
int pr[255][222222], d[333];
void add(int &x, int y) {
  x += y;
  if (x < 0) x += mod;
  if (x >= mod) x -= mod;
}
void Add(int l, int r, int R) {
  while (r >= l && r / magic == R / magic) {
    b[r]++;
    r--;
  }
  if (l > r) return;
  int lb = l / magic, rb = r / magic;
  if (lb == rb) {
    for (int i = l; i <= r; i++) {
      add(pr[lb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
  } else {
    for (int i = l; i < (lb + 1) * magic; i++) {
      add(pr[lb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
    for (int i = rb * magic; i <= r; i++) {
      add(pr[rb][b[i] + maxn], -dp[i - 1]);
      b[i]++;
    }
    for (int i = lb + 1; i < rb; i++) {
      d[i]++;
    }
  }
}
void del(int l, int r, int R) {
  while (r >= l && r / magic == R / magic) {
    b[r]--;
    r--;
  }
  if (l > r) return;
  int lb = l / magic, rb = r / magic;
  if (lb == rb) {
    for (int i = l; i <= r; i++) {
      add(pr[lb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
  } else {
    for (int i = l; i < (lb + 1) * magic; i++) {
      add(pr[lb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
    for (int i = rb * magic; i <= r; i++) {
      add(pr[rb][b[i] - 1 + maxn], dp[i - 1]);
      b[i]--;
    }
    for (int i = lb + 1; i < rb; i++) {
      d[i]--;
    }
  }
}
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++) {
    pre[i] = cur[a[i]];
    cur[a[i]] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    Add(pre[i] + 1, i, i + 1);
    if (pre[i]) del(pre[pre[i]] + 1, pre[i], i + 1);
    for (int j = i; j / magic == (i + 1) / magic && j > 0; j--) {
      if (b[j] <= k) add(dp[i], dp[j - 1]);
    }
    for (int j = (i + 1) / magic - 1; j >= 0; j--) {
      add(dp[i], pr[j][k - d[j] + maxn]);
    }
    if ((i + 1) % magic == magic - 1) {
      for (int j = i + 1; j / magic == (i + 1) / magic && j > 0; j--) {
        add(pr[j / magic][b[j] + maxn], dp[j - 1]);
      }
      for (int j = 1; j <= n + 2; j++)
        add(pr[(i + 1) / magic][j + maxn], pr[(i + 1) / magic][j - 1 + maxn]);
    }
  }
  if (n == 10000 && k == 10000 && dp[n] != 430192466) {
    for (int i = 2; i <= n; i++) {
      if (dp[i] != dp[i - 1] * 2 % mod) {
        cout << i << " " << dp[i] << " " << dp[i - 1] << endl;
      }
    }
    return 0;
  }
  printf("%d\n", dp[n]);
  return 0;
}

```