#include <bits/stdc++.h>
using namespace std;
int n, k, a[200010], s, la[200010], f[200010], tg[200010], ans, p[200010],
    va[320][200010], pr[200010];
int bl(int x) { return (x - 1) / s + 1; }
void ins(int x, int y) {
  p[x] -= tg[bl(x)];
  ans = (ans + y) % 998244353ll;
  va[bl(x)][p[x] + n] = (va[bl(x)][p[x] + n] + y) % 998244353ll;
}
void md(int x, int y) {
  int po = bl(x);
  if (p[x] + tg[po] <= k) ans = (ans - f[x - 1] + 998244353ll) % 998244353ll;
  va[po][p[x] + n] = (va[po][p[x] + n] + 998244353ll - f[x - 1]) % 998244353ll;
  p[x] += y;
  if (p[x] + tg[po] <= k) ans = (ans + f[x - 1]) % 998244353ll;
  va[po][p[x] + n] = (va[po][p[x] + n] + f[x - 1]) % 998244353ll;
}
void mod(int l, int r, int v) {
  if (l > r) return;
  int p1 = bl(l), p2 = bl(r);
  if (p1 + 1 >= p2) {
    for (int i = l; i <= r; i++) md(i, v);
  } else {
    for (int i = l; i <= s * p1; i++) md(i, v);
    for (int i = (p2 - 1) * s + 1; i <= r; i++) md(i, v);
    for (int i = p1 + 1; i < p2; i++) {
      if (v != -1)
        ans = (ans - va[i][k - tg[i] + n] + 998244353ll) % 998244353ll;
      else
        ans = (ans + va[i][k - tg[i] + 1 + n]) % 998244353ll;
      tg[i] += v;
    }
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pr[i] = la[a[i]];
    la[a[i]] = i;
  }
  s = sqrt(n);
  f[0] = 1;
  ins(1, 1);
  for (int i = 1; i <= n; i++) {
    mod(pr[i] + 1, i, 1);
    mod(pr[pr[i]] + 1, pr[i], -1);
    f[i] = ans;
    ins(i + 1, ans);
  }
  cout << f[n];
}

### Prompt

Your task is to create 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;
int n, k, a[200010], s, la[200010], f[200010], tg[200010], ans, p[200010],
    va[320][200010], pr[200010];
int bl(int x) { return (x - 1) / s + 1; }
void ins(int x, int y) {
  p[x] -= tg[bl(x)];
  ans = (ans + y) % 998244353ll;
  va[bl(x)][p[x] + n] = (va[bl(x)][p[x] + n] + y) % 998244353ll;
}
void md(int x, int y) {
  int po = bl(x);
  if (p[x] + tg[po] <= k) ans = (ans - f[x - 1] + 998244353ll) % 998244353ll;
  va[po][p[x] + n] = (va[po][p[x] + n] + 998244353ll - f[x - 1]) % 998244353ll;
  p[x] += y;
  if (p[x] + tg[po] <= k) ans = (ans + f[x - 1]) % 998244353ll;
  va[po][p[x] + n] = (va[po][p[x] + n] + f[x - 1]) % 998244353ll;
}
void mod(int l, int r, int v) {
  if (l > r) return;
  int p1 = bl(l), p2 = bl(r);
  if (p1 + 1 >= p2) {
    for (int i = l; i <= r; i++) md(i, v);
  } else {
    for (int i = l; i <= s * p1; i++) md(i, v);
    for (int i = (p2 - 1) * s + 1; i <= r; i++) md(i, v);
    for (int i = p1 + 1; i < p2; i++) {
      if (v != -1)
        ans = (ans - va[i][k - tg[i] + n] + 998244353ll) % 998244353ll;
      else
        ans = (ans + va[i][k - tg[i] + 1 + n]) % 998244353ll;
      tg[i] += v;
    }
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pr[i] = la[a[i]];
    la[a[i]] = i;
  }
  s = sqrt(n);
  f[0] = 1;
  ins(1, 1);
  for (int i = 1; i <= n; i++) {
    mod(pr[i] + 1, i, 1);
    mod(pr[pr[i]] + 1, pr[i], -1);
    f[i] = ans;
    ins(i + 1, ans);
  }
  cout << f[n];
}

```