#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int tzu = 500;
int bs = 350;
int n, k;
int a[100001];
int l[100001];
int p[100001];
int dp[100001];
int v[100001];
int sum[501];
int cnt[501][1001];
int mn[501], mx[501];
int m;
void ref(int bl) {
  int curv = tzu;
  for (int i = mn[bl]; i <= mx[bl]; i++) cnt[bl][i] = 0;
  mn[bl] = mx[bl] = tzu;
  for (int i = min(m, bl * bs); i > (bl - 1) * bs; i--) {
    curv += v[i];
    cnt[bl][curv] += dp[i - 1];
    if (cnt[bl][curv] >= mod) cnt[bl][curv] -= mod;
    mn[bl] = min(mn[bl], curv);
    mx[bl] = max(mx[bl], curv);
  }
  for (int i = mn[bl] + 1; i <= mx[bl]; i++) {
    cnt[bl][i] += cnt[bl][i - 1];
    if (cnt[bl][i] >= mod) cnt[bl][i] -= mod;
  }
  sum[bl] = curv;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    l[i] = p[a[i]];
    p[a[i]] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    m = i;
    set<int> upd;
    v[i] = 1;
    upd.insert((i - 1) / bs + 1);
    if (l[i] != 0) {
      v[l[i]] = -1;
      upd.insert((l[i] - 1) / bs + 1);
      if (l[l[i]] != 0) v[l[l[i]]] = 0;
      upd.insert((l[l[i]] - 1) / bs + 1);
    }
    for (auto cur : upd) ref(cur);
    int cb = (i - 1) / bs + 1;
    int cs = 0;
    for (int j = cb; j >= 1; j--) {
      if (tzu + k - cs >= 0) dp[i] += cnt[j][min(mx[j], tzu + k - cs)];
      cs += sum[j] - tzu;
      if (dp[i] >= mod) dp[i] -= mod;
    }
  }
  cout << dp[n] << endl;
}

### Prompt

Please create a solution in cpp 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 long long mod = 998244353;
const int tzu = 500;
int bs = 350;
int n, k;
int a[100001];
int l[100001];
int p[100001];
int dp[100001];
int v[100001];
int sum[501];
int cnt[501][1001];
int mn[501], mx[501];
int m;
void ref(int bl) {
  int curv = tzu;
  for (int i = mn[bl]; i <= mx[bl]; i++) cnt[bl][i] = 0;
  mn[bl] = mx[bl] = tzu;
  for (int i = min(m, bl * bs); i > (bl - 1) * bs; i--) {
    curv += v[i];
    cnt[bl][curv] += dp[i - 1];
    if (cnt[bl][curv] >= mod) cnt[bl][curv] -= mod;
    mn[bl] = min(mn[bl], curv);
    mx[bl] = max(mx[bl], curv);
  }
  for (int i = mn[bl] + 1; i <= mx[bl]; i++) {
    cnt[bl][i] += cnt[bl][i - 1];
    if (cnt[bl][i] >= mod) cnt[bl][i] -= mod;
  }
  sum[bl] = curv;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    l[i] = p[a[i]];
    p[a[i]] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    m = i;
    set<int> upd;
    v[i] = 1;
    upd.insert((i - 1) / bs + 1);
    if (l[i] != 0) {
      v[l[i]] = -1;
      upd.insert((l[i] - 1) / bs + 1);
      if (l[l[i]] != 0) v[l[l[i]]] = 0;
      upd.insert((l[l[i]] - 1) / bs + 1);
    }
    for (auto cur : upd) ref(cur);
    int cb = (i - 1) / bs + 1;
    int cs = 0;
    for (int j = cb; j >= 1; j--) {
      if (tzu + k - cs >= 0) dp[i] += cnt[j][min(mx[j], tzu + k - cs)];
      cs += sum[j] - tzu;
      if (dp[i] >= mod) dp[i] -= mod;
    }
  }
  cout << dp[n] << endl;
}

```