#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkMax(T &x, T y) {
  if (y > x) x = y;
}
template <typename T>
void chkMin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void inline read(T &x) {
  int f = 1;
  x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
  x *= f;
}
template <typename T>
void print(T x) {
  if (x < 0) {
    putchar('-');
    print(-x);
    return;
  }
  if (x >= 10) print(x / 10);
  putchar((x % 10) + '0');
}
const int N = 1e5 + 5, S = 325, P = 998244353;
int n, k, a[N], tag[N], c[N], L[N], R[N], pos[N], t, pre[N], cnt[N];
int f[N];
vector<pair<int, int> > b[N];
void inline add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
void inline rebuild(int p) {
  b[p].clear();
  for (int i = L[p]; i <= R[p]; i++) {
    c[i] += tag[p];
    b[p].push_back(make_pair(c[i], f[i]));
  }
  tag[p] = 0;
  sort(b[p].begin(), b[p].end());
  for (int i = 1; i < b[p].size(); i++) add(b[p][i].second, b[p][i - 1].second);
}
void inline add(int l, int r, int k) {
  if (l == 0) l++;
  int p = pos[l], q = pos[r];
  if (p == q) {
    for (int i = l; i <= r; i++) {
      c[i] += k;
    }
    rebuild(p);
  } else {
    for (int i = l; i <= R[p]; i++) c[i] += k;
    rebuild(p);
    for (int i = p + 1; i < q; i++) {
      tag[i] += k;
    }
    for (int i = L[q]; i <= r; i++) c[i] += k;
    rebuild(q);
  }
}
int inline query(int l, int r) {
  int p = pos[l], q = pos[r], res = 0;
  if (p == q) {
    for (int i = l; i <= r; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
  } else {
    for (int i = l; i <= R[p]; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
    for (int i = L[q]; i <= r; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
    for (int i = p + 1; i < q; i++) {
      int t =
          upper_bound(b[i].begin(), b[i].end(), make_pair(k - tag[i] + 1, 0)) -
          b[i].begin() - 1;
      if (t >= 0) add(res, b[i][t].second);
    }
  }
  return res;
}
int main() {
  read(n), read(k);
  ++n;
  t = sqrt(n);
  for (int i = 1; i <= n; i++) {
    pos[i] = (i - 1) / t + 1;
    if (!L[pos[i]]) L[pos[i]] = i;
    R[pos[i]] = i;
  }
  for (int i = 2; i <= n; i++) {
    read(a[i]);
    pre[i] = cnt[a[i]];
    cnt[a[i]] = i;
  }
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (pre[i]) {
      int t = pre[i];
      add(pre[t], t - 1, -1);
    }
    add(pre[i], i - 1, 1);
    f[i] = query(1, i - 1);
    if (R[pos[i]] == i) rebuild(pos[i]);
  }
  printf("%d\n", f[n]);
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
template <typename T>
void chkMax(T &x, T y) {
  if (y > x) x = y;
}
template <typename T>
void chkMin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void inline read(T &x) {
  int f = 1;
  x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
  x *= f;
}
template <typename T>
void print(T x) {
  if (x < 0) {
    putchar('-');
    print(-x);
    return;
  }
  if (x >= 10) print(x / 10);
  putchar((x % 10) + '0');
}
const int N = 1e5 + 5, S = 325, P = 998244353;
int n, k, a[N], tag[N], c[N], L[N], R[N], pos[N], t, pre[N], cnt[N];
int f[N];
vector<pair<int, int> > b[N];
void inline add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
void inline rebuild(int p) {
  b[p].clear();
  for (int i = L[p]; i <= R[p]; i++) {
    c[i] += tag[p];
    b[p].push_back(make_pair(c[i], f[i]));
  }
  tag[p] = 0;
  sort(b[p].begin(), b[p].end());
  for (int i = 1; i < b[p].size(); i++) add(b[p][i].second, b[p][i - 1].second);
}
void inline add(int l, int r, int k) {
  if (l == 0) l++;
  int p = pos[l], q = pos[r];
  if (p == q) {
    for (int i = l; i <= r; i++) {
      c[i] += k;
    }
    rebuild(p);
  } else {
    for (int i = l; i <= R[p]; i++) c[i] += k;
    rebuild(p);
    for (int i = p + 1; i < q; i++) {
      tag[i] += k;
    }
    for (int i = L[q]; i <= r; i++) c[i] += k;
    rebuild(q);
  }
}
int inline query(int l, int r) {
  int p = pos[l], q = pos[r], res = 0;
  if (p == q) {
    for (int i = l; i <= r; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
  } else {
    for (int i = l; i <= R[p]; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
    for (int i = L[q]; i <= r; i++)
      if (c[i] + tag[p] <= k) add(res, f[i]);
    for (int i = p + 1; i < q; i++) {
      int t =
          upper_bound(b[i].begin(), b[i].end(), make_pair(k - tag[i] + 1, 0)) -
          b[i].begin() - 1;
      if (t >= 0) add(res, b[i][t].second);
    }
  }
  return res;
}
int main() {
  read(n), read(k);
  ++n;
  t = sqrt(n);
  for (int i = 1; i <= n; i++) {
    pos[i] = (i - 1) / t + 1;
    if (!L[pos[i]]) L[pos[i]] = i;
    R[pos[i]] = i;
  }
  for (int i = 2; i <= n; i++) {
    read(a[i]);
    pre[i] = cnt[a[i]];
    cnt[a[i]] = i;
  }
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (pre[i]) {
      int t = pre[i];
      add(pre[t], t - 1, -1);
    }
    add(pre[i], i - 1, 1);
    f[i] = query(1, i - 1);
    if (R[pos[i]] == i) rebuild(pos[i]);
  }
  printf("%d\n", f[n]);
  return 0;
}

```