#include <bits/stdc++.h>
using namespace std;
const int B = 320;
const int N = 100000;
const int P = 998244353;
inline int add(int x, int y) {
  x += y;
  return x >= P ? x - P : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + P : x;
}
inline int mul(int x, int y) { return (int)(1LL * x * y % P); }
int n, k;
int le[N + 5], ri[N + 5], id[N + 5], bcnt;
void build() {
  for (int i = 1; i <= n; i++) {
    if ((i - 1) % B == 0) le[++bcnt] = i;
    ri[bcnt] = i, id[i] = bcnt;
  }
}
int c[N + 5], dp[N + 5];
int s[B + 5][B + 5], tg[B + 5], lb[B + 5];
void pushtag(int x) {
  if (!tg[x]) return;
  for (int i = le[x]; i <= ri[x]; i++) c[i] += tg[x];
  tg[x] = 0;
}
void rebuild(int x) {
  lb[x] = 10 * N + 5;
  for (int i = 0; i <= B; i++) s[x][i] = 0;
  for (int i = le[x]; i <= ri[x]; i++) lb[x] = min(lb[x], c[i]);
  for (int i = le[x]; i <= ri[x]; i++)
    s[x][c[i] - lb[x]] = add(s[x][c[i] - lb[x]], dp[i - 1]);
  for (int i = 1; i <= B; i++) s[x][i] = add(s[x][i], s[x][i - 1]);
}
void add(int l, int r, int d) {
  int p = id[l], q = id[r];
  if (p == q) {
    pushtag(p);
    for (int i = l; i <= r; i++) c[i] += d;
    rebuild(p);
  } else {
    pushtag(p);
    for (int i = l; i <= ri[p]; i++) c[i] += d;
    rebuild(p);
    for (int i = p + 1; i <= q - 1; i++) tg[i] += d;
    pushtag(q);
    for (int i = le[q]; i <= r; i++) c[i] += d;
    rebuild(q);
  }
}
int query() {
  int ret = 0;
  for (int i = 1; i <= bcnt; i++) {
    if (lb[i] + tg[i] <= k) {
      if (lb[i] + tg[i] + B <= k)
        ret = add(ret, s[i][B]);
      else
        ret = add(ret, s[i][k - lb[i] - tg[i]]);
    }
  }
  return ret;
}
int a[N + 5], b[N + 5], lst[N + 5];
int main() {
  scanf("%d%d", &n, &k), build();
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]), lst[i] = b[a[i]], b[a[i]] = i;
  dp[0] = 1, rebuild(1);
  for (int i = 1; i <= n; i++) {
    add(lst[i] + 1, i, 1);
    if (lst[i]) add(lst[lst[i]] + 1, lst[i], -1);
    dp[i] = query(), rebuild(id[i + 1]);
  }
  printf("%d\n", dp[n]);
}

### 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 B = 320;
const int N = 100000;
const int P = 998244353;
inline int add(int x, int y) {
  x += y;
  return x >= P ? x - P : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + P : x;
}
inline int mul(int x, int y) { return (int)(1LL * x * y % P); }
int n, k;
int le[N + 5], ri[N + 5], id[N + 5], bcnt;
void build() {
  for (int i = 1; i <= n; i++) {
    if ((i - 1) % B == 0) le[++bcnt] = i;
    ri[bcnt] = i, id[i] = bcnt;
  }
}
int c[N + 5], dp[N + 5];
int s[B + 5][B + 5], tg[B + 5], lb[B + 5];
void pushtag(int x) {
  if (!tg[x]) return;
  for (int i = le[x]; i <= ri[x]; i++) c[i] += tg[x];
  tg[x] = 0;
}
void rebuild(int x) {
  lb[x] = 10 * N + 5;
  for (int i = 0; i <= B; i++) s[x][i] = 0;
  for (int i = le[x]; i <= ri[x]; i++) lb[x] = min(lb[x], c[i]);
  for (int i = le[x]; i <= ri[x]; i++)
    s[x][c[i] - lb[x]] = add(s[x][c[i] - lb[x]], dp[i - 1]);
  for (int i = 1; i <= B; i++) s[x][i] = add(s[x][i], s[x][i - 1]);
}
void add(int l, int r, int d) {
  int p = id[l], q = id[r];
  if (p == q) {
    pushtag(p);
    for (int i = l; i <= r; i++) c[i] += d;
    rebuild(p);
  } else {
    pushtag(p);
    for (int i = l; i <= ri[p]; i++) c[i] += d;
    rebuild(p);
    for (int i = p + 1; i <= q - 1; i++) tg[i] += d;
    pushtag(q);
    for (int i = le[q]; i <= r; i++) c[i] += d;
    rebuild(q);
  }
}
int query() {
  int ret = 0;
  for (int i = 1; i <= bcnt; i++) {
    if (lb[i] + tg[i] <= k) {
      if (lb[i] + tg[i] + B <= k)
        ret = add(ret, s[i][B]);
      else
        ret = add(ret, s[i][k - lb[i] - tg[i]]);
    }
  }
  return ret;
}
int a[N + 5], b[N + 5], lst[N + 5];
int main() {
  scanf("%d%d", &n, &k), build();
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]), lst[i] = b[a[i]], b[a[i]] = i;
  dp[0] = 1, rebuild(1);
  for (int i = 1; i <= n; i++) {
    add(lst[i] + 1, i, 1);
    if (lst[i]) add(lst[lst[i]] + 1, lst[i], -1);
    dp[i] = query(), rebuild(id[i + 1]);
  }
  printf("%d\n", dp[n]);
}

```