#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
int add(int a, int b) { return a + b >= Mod ? a + b - Mod : a + b; }
void Add(int &a, int b) { a = add(a, b); }
int dec(int a, int b) { return a - b < 0 ? a - b + Mod : a - b; }
void Dec(int &a, int b) { a = dec(a, b); }
const int N = 1e5 + 50, M = 300, A = 1e5;
int n, k, S, ct, a[N], pre[N], blk[N], dp[N];
int b[N], t[M], bin[M][N + A], sm[M], L[N], R[N];
void ins(int u, int vl) {
  int p = blk[u];
  Add(sm[p], vl);
  Add(bin[p][b[u] - t[p] + A], vl);
}
void mdf(int i, int lp, int v) {
  if (b[i] + t[lp] <= k) Dec(sm[lp], dp[i - 1]);
  Dec(bin[lp][b[i] + A], dp[i - 1]);
  b[i] += v;
  if (b[i] + t[lp] <= k) Add(sm[lp], dp[i - 1]);
  Add(bin[lp][b[i] + A], dp[i - 1]);
}
void add(int l, int r, int v) {
  if (l > r) return;
  int lp = blk[l], rp = blk[r];
  if (blk[l] == blk[r]) {
    for (int i = l; i <= r; i++) mdf(i, lp, v);
    return;
  }
  for (int i = l; i <= R[lp]; i++) mdf(i, lp, v);
  for (int i = L[rp]; i <= r; i++) mdf(i, rp, v);
  for (int i = lp + 1; i < rp; i++) {
    if (v > 0)
      Dec(sm[i], bin[i][k - t[i] + A]);
    else
      Add(sm[i], bin[i][k - t[i] + 1 + A]);
    t[i] += v;
  }
}
int qry(int p) {
  int ans = 0, c = 0;
  for (; c <= ct && R[c] <= p; c++) Add(ans, sm[c]);
  if (c > ct) return ans;
  for (int i = L[c]; i <= p; i++)
    if (b[i] + t[c] <= k) Add(ans, dp[i - 1]);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  S = 350;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  static int ls[N];
  for (int i = 1; i <= n; i++) pre[i] = ls[a[i]], ls[a[i]] = i;
  for (int i = 1; i <= n; i++) blk[i] = (i - 1) / S + 1;
  for (int i = 1; i <= n; i += S) L[++ct] = i, R[ct] = i + S - 1;
  R[ct] = n;
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    ins(i, dp[i - 1]);
    add(pre[i] + 1, i, 1);
    add(pre[pre[i]] + 1, pre[i], -1);
    dp[i] = qry(i);
  }
  cout << dp[n];
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 Mod = 998244353;
int add(int a, int b) { return a + b >= Mod ? a + b - Mod : a + b; }
void Add(int &a, int b) { a = add(a, b); }
int dec(int a, int b) { return a - b < 0 ? a - b + Mod : a - b; }
void Dec(int &a, int b) { a = dec(a, b); }
const int N = 1e5 + 50, M = 300, A = 1e5;
int n, k, S, ct, a[N], pre[N], blk[N], dp[N];
int b[N], t[M], bin[M][N + A], sm[M], L[N], R[N];
void ins(int u, int vl) {
  int p = blk[u];
  Add(sm[p], vl);
  Add(bin[p][b[u] - t[p] + A], vl);
}
void mdf(int i, int lp, int v) {
  if (b[i] + t[lp] <= k) Dec(sm[lp], dp[i - 1]);
  Dec(bin[lp][b[i] + A], dp[i - 1]);
  b[i] += v;
  if (b[i] + t[lp] <= k) Add(sm[lp], dp[i - 1]);
  Add(bin[lp][b[i] + A], dp[i - 1]);
}
void add(int l, int r, int v) {
  if (l > r) return;
  int lp = blk[l], rp = blk[r];
  if (blk[l] == blk[r]) {
    for (int i = l; i <= r; i++) mdf(i, lp, v);
    return;
  }
  for (int i = l; i <= R[lp]; i++) mdf(i, lp, v);
  for (int i = L[rp]; i <= r; i++) mdf(i, rp, v);
  for (int i = lp + 1; i < rp; i++) {
    if (v > 0)
      Dec(sm[i], bin[i][k - t[i] + A]);
    else
      Add(sm[i], bin[i][k - t[i] + 1 + A]);
    t[i] += v;
  }
}
int qry(int p) {
  int ans = 0, c = 0;
  for (; c <= ct && R[c] <= p; c++) Add(ans, sm[c]);
  if (c > ct) return ans;
  for (int i = L[c]; i <= p; i++)
    if (b[i] + t[c] <= k) Add(ans, dp[i - 1]);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  S = 350;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  static int ls[N];
  for (int i = 1; i <= n; i++) pre[i] = ls[a[i]], ls[a[i]] = i;
  for (int i = 1; i <= n; i++) blk[i] = (i - 1) / S + 1;
  for (int i = 1; i <= n; i += S) L[++ct] = i, R[ct] = i + S - 1;
  R[ct] = n;
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    ins(i, dp[i - 1]);
    add(pre[i] + 1, i, 1);
    add(pre[pre[i]] + 1, pre[i], -1);
    dp[i] = qry(i);
  }
  cout << dp[n];
  return 0;
}

```