#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int ch = 0, f = 0;
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  if (f) x = -x;
}
const int M = 205, N = 100005, L = 100000, mod = 998244353;
int a[N], bel[N], tag[N], tot[N], ans[M], s[M][N << 1], pre[N], lst[N], dp[N],
    n, k, T;
inline void up(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void gao(int i, int x) {
  up(s[bel[i]][L + tot[i]], mod - dp[i]);
  tot[i] += x;
  up(s[bel[i]][L + tot[i]], dp[i]);
  if (x == 1 && tot[i] + tag[bel[i]] == k + 1) up(ans[bel[i]], mod - dp[i]);
  if (x == -1 && tot[i] + tag[bel[i]] == k) up(ans[bel[i]], dp[i]);
}
inline void modify(int l, int r, int x) {
  if (bel[l] + 1 >= bel[r]) {
    for (int i = l; i <= r; i++) gao(i, x);
    return;
  }
  for (int i = l; i < (bel[l] + 1) * T; i++) gao(i, x);
  for (int i = bel[r] * T; i <= r; i++) gao(i, x);
  for (int i = bel[l] + 1; i < bel[r]; i++) {
    if (x == 1) up(ans[i], mod - s[i][L + k - tag[i]]);
    if (x == -1) up(ans[i], s[i][L + k - tag[i] + 1]);
    tag[i] += x;
  }
}
inline int query(int l, int r) {
  int res = 0;
  if (bel[l] + 1 >= bel[r]) {
    for (int i = l; i <= r; i++)
      if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
    return res;
  }
  for (int i = l; i < (bel[l] + 1) * T; i++)
    if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
  for (int i = bel[r] * T; i <= r; i++)
    if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
  for (int i = bel[l] + 1; i < bel[r]; i++) up(res, ans[i]);
  return res;
}
int main() {
  read(n), read(k), T = 500;
  for (int i = 0; i <= n; i++) bel[i] = i / T;
  for (int i = 1; i <= n; i++) read(a[i]);
  dp[0] = 1;
  up(ans[bel[0]], dp[0]);
  up(s[bel[0]][L - tag[bel[0]]], dp[0]);
  for (int i = 1; i <= n; i++) {
    pre[i] = lst[a[i]], lst[a[i]] = i;
    modify(pre[i], i - 1, 1);
    if (pre[i]) modify(pre[pre[i]], pre[i] - 1, -1);
    dp[i] = query(0, i - 1);
    up(ans[bel[i]], dp[i]);
    up(s[bel[i]][L - tag[bel[i]]], dp[i]);
  }
  cout << dp[n];
  return 0;
}

### Prompt

Develop a solution in cpp 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 <class T>
inline void read(T &x) {
  int ch = 0, f = 0;
  x = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  if (f) x = -x;
}
const int M = 205, N = 100005, L = 100000, mod = 998244353;
int a[N], bel[N], tag[N], tot[N], ans[M], s[M][N << 1], pre[N], lst[N], dp[N],
    n, k, T;
inline void up(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void gao(int i, int x) {
  up(s[bel[i]][L + tot[i]], mod - dp[i]);
  tot[i] += x;
  up(s[bel[i]][L + tot[i]], dp[i]);
  if (x == 1 && tot[i] + tag[bel[i]] == k + 1) up(ans[bel[i]], mod - dp[i]);
  if (x == -1 && tot[i] + tag[bel[i]] == k) up(ans[bel[i]], dp[i]);
}
inline void modify(int l, int r, int x) {
  if (bel[l] + 1 >= bel[r]) {
    for (int i = l; i <= r; i++) gao(i, x);
    return;
  }
  for (int i = l; i < (bel[l] + 1) * T; i++) gao(i, x);
  for (int i = bel[r] * T; i <= r; i++) gao(i, x);
  for (int i = bel[l] + 1; i < bel[r]; i++) {
    if (x == 1) up(ans[i], mod - s[i][L + k - tag[i]]);
    if (x == -1) up(ans[i], s[i][L + k - tag[i] + 1]);
    tag[i] += x;
  }
}
inline int query(int l, int r) {
  int res = 0;
  if (bel[l] + 1 >= bel[r]) {
    for (int i = l; i <= r; i++)
      if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
    return res;
  }
  for (int i = l; i < (bel[l] + 1) * T; i++)
    if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
  for (int i = bel[r] * T; i <= r; i++)
    if (tot[i] + tag[bel[i]] <= k) up(res, dp[i]);
  for (int i = bel[l] + 1; i < bel[r]; i++) up(res, ans[i]);
  return res;
}
int main() {
  read(n), read(k), T = 500;
  for (int i = 0; i <= n; i++) bel[i] = i / T;
  for (int i = 1; i <= n; i++) read(a[i]);
  dp[0] = 1;
  up(ans[bel[0]], dp[0]);
  up(s[bel[0]][L - tag[bel[0]]], dp[0]);
  for (int i = 1; i <= n; i++) {
    pre[i] = lst[a[i]], lst[a[i]] = i;
    modify(pre[i], i - 1, 1);
    if (pre[i]) modify(pre[pre[i]], pre[i] - 1, -1);
    dp[i] = query(0, i - 1);
    up(ans[bel[i]], dp[i]);
    up(s[bel[i]][L - tag[bel[i]]], dp[i]);
  }
  cout << dp[n];
  return 0;
}

```