#include <bits/stdc++.h>
const int Bs = 317, N = 2e5 + 10, mod = 998244353;
int ri() {
  char c = getchar();
  int x = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c;
  return x * f;
}
int pr[N], las[N], a[N], val[Bs][N], sum[N], f[N], tag[Bs], B, ans, k, n;
int belong(int x) { return (x - 1) / B + 1; }
void sub(int &a, int b, int P) {
  a -= b;
  if (a < 0) a += P;
}
void add(int &a, int b, int P) {
  a += b;
  if (a >= P) a -= P;
}
inline void insert(int u, int v) {
  int bu = belong(u);
  sum[u] -= tag[bu];
  add(ans, v, mod);
  add(val[bu][sum[u] + n], v, mod);
}
void change(int u, int v) {
  int bu = belong(u);
  if (sum[u] + tag[bu] <= k) sub(ans, f[u - 1], mod);
  sub(val[bu][sum[u] + n], f[u - 1], mod);
  sum[u] += v;
  if (sum[u] + tag[bu] <= k) add(ans, f[u - 1], mod);
  add(val[bu][sum[u] + n], f[u - 1], mod);
}
inline void modify(int l, int r, int v) {
  if (l > r) return;
  int bl = belong(l), br = belong(r);
  if (bl + 1 >= br) {
    for (int i = l; i <= r; i++) change(i, v);
  } else {
    for (int i = l; i <= B * bl; i++) change(i, v);
    for (int i = B * (br - 1) + 1; i <= r; i++) change(i, v);
    for (int i = bl + 1; i < br; i++) {
      if (~v)
        sub(ans, val[i][k - tag[i] + n], mod);
      else
        add(ans, val[i][k - tag[i] + 1 + n], mod);
      tag[i] += v;
    }
  }
}
int main() {
  n = ri();
  k = ri();
  for (int i = 1, a; i <= n; ++i) a = ri(), pr[i] = las[a], las[a] = i;
  B = sqrt(n);
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    insert(i, f[i - 1]);
    modify(pr[i] + 1, i, 1);
    modify(pr[pr[i]] + 1, pr[i], -1);
    f[i] = ans;
  }
  printf("%d\n", f[n]);
  return 0;
}

### Prompt

Generate 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>
const int Bs = 317, N = 2e5 + 10, mod = 998244353;
int ri() {
  char c = getchar();
  int x = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c;
  return x * f;
}
int pr[N], las[N], a[N], val[Bs][N], sum[N], f[N], tag[Bs], B, ans, k, n;
int belong(int x) { return (x - 1) / B + 1; }
void sub(int &a, int b, int P) {
  a -= b;
  if (a < 0) a += P;
}
void add(int &a, int b, int P) {
  a += b;
  if (a >= P) a -= P;
}
inline void insert(int u, int v) {
  int bu = belong(u);
  sum[u] -= tag[bu];
  add(ans, v, mod);
  add(val[bu][sum[u] + n], v, mod);
}
void change(int u, int v) {
  int bu = belong(u);
  if (sum[u] + tag[bu] <= k) sub(ans, f[u - 1], mod);
  sub(val[bu][sum[u] + n], f[u - 1], mod);
  sum[u] += v;
  if (sum[u] + tag[bu] <= k) add(ans, f[u - 1], mod);
  add(val[bu][sum[u] + n], f[u - 1], mod);
}
inline void modify(int l, int r, int v) {
  if (l > r) return;
  int bl = belong(l), br = belong(r);
  if (bl + 1 >= br) {
    for (int i = l; i <= r; i++) change(i, v);
  } else {
    for (int i = l; i <= B * bl; i++) change(i, v);
    for (int i = B * (br - 1) + 1; i <= r; i++) change(i, v);
    for (int i = bl + 1; i < br; i++) {
      if (~v)
        sub(ans, val[i][k - tag[i] + n], mod);
      else
        add(ans, val[i][k - tag[i] + 1 + n], mod);
      tag[i] += v;
    }
  }
}
int main() {
  n = ri();
  k = ri();
  for (int i = 1, a; i <= n; ++i) a = ri(), pr[i] = las[a], las[a] = i;
  B = sqrt(n);
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    insert(i, f[i - 1]);
    modify(pr[i] + 1, i, 1);
    modify(pr[pr[i]] + 1, pr[i], -1);
    f[i] = ans;
  }
  printf("%d\n", f[n]);
  return 0;
}

```