#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 100005;
const int B = 620;
int n, k, a[N];
int dp[N];
int cnt[N];
vector<int> occ[N];
int delta[B];
vector<int> vet[B];
vector<int> psum[B];
void add(int &aa, int b) { aa = aa + b >= mod ? aa + b - mod : aa + b; }
void rebuild(int id) {
  sort(vet[id].begin(), vet[id].end(),
       [=](int q, int w) { return cnt[q] < cnt[w]; });
  for (int i = 0; i < (int)vet[id].size(); i++) {
    if (!i)
      psum[id][i] = 0;
    else
      psum[id][i] = psum[id][i - 1];
    add(psum[id][i], dp[vet[id][i] - 1]);
  }
}
void add(int L, int R, int val) {
  int ida = L / B, idb = R / B;
  if (ida == idb) {
    for (int i = L; i <= R; i++) cnt[i] += val;
    rebuild(ida);
    return;
  }
  for (int i = L; ida == i / B; i++) cnt[i] += val;
  for (int i = idb * B; i <= R; i++) cnt[i] += val;
  rebuild(ida);
  rebuild(idb);
  for (int i = ida + 1; i < idb; i++) delta[i] += val;
}
int get(int id) {
  vector<int> &v = vet[id];
  int L = 0, R = (int)v.size() - 1, ans = (int)v.size();
  while (L <= R) {
    int mid = (L + R) / 2;
    if (cnt[v[mid]] + delta[id] > k) {
      ans = mid;
      R = mid - 1;
    } else
      L = mid + 1;
  }
  if (!ans) return 0;
  return psum[id][ans - 1];
}
int query(int lim) {
  int ans = 0;
  for (int id = 0; id <= lim / B; id++) {
    add(ans, get(id));
  }
  return ans;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) {
    occ[i].push_back(0);
    occ[i].push_back(0);
    vet[i / B].push_back(i);
    psum[i / B].push_back(0);
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    vector<int> &v = occ[a[i]];
    add(v[v.size() - 2] + 1, v.back(), -1);
    add(v.back() + 1, i, +1);
    occ[a[i]].push_back(i);
    dp[i] = query(i);
  }
  cout << dp[n] << endl;
}

### 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;
const int mod = 998244353;
const int N = 100005;
const int B = 620;
int n, k, a[N];
int dp[N];
int cnt[N];
vector<int> occ[N];
int delta[B];
vector<int> vet[B];
vector<int> psum[B];
void add(int &aa, int b) { aa = aa + b >= mod ? aa + b - mod : aa + b; }
void rebuild(int id) {
  sort(vet[id].begin(), vet[id].end(),
       [=](int q, int w) { return cnt[q] < cnt[w]; });
  for (int i = 0; i < (int)vet[id].size(); i++) {
    if (!i)
      psum[id][i] = 0;
    else
      psum[id][i] = psum[id][i - 1];
    add(psum[id][i], dp[vet[id][i] - 1]);
  }
}
void add(int L, int R, int val) {
  int ida = L / B, idb = R / B;
  if (ida == idb) {
    for (int i = L; i <= R; i++) cnt[i] += val;
    rebuild(ida);
    return;
  }
  for (int i = L; ida == i / B; i++) cnt[i] += val;
  for (int i = idb * B; i <= R; i++) cnt[i] += val;
  rebuild(ida);
  rebuild(idb);
  for (int i = ida + 1; i < idb; i++) delta[i] += val;
}
int get(int id) {
  vector<int> &v = vet[id];
  int L = 0, R = (int)v.size() - 1, ans = (int)v.size();
  while (L <= R) {
    int mid = (L + R) / 2;
    if (cnt[v[mid]] + delta[id] > k) {
      ans = mid;
      R = mid - 1;
    } else
      L = mid + 1;
  }
  if (!ans) return 0;
  return psum[id][ans - 1];
}
int query(int lim) {
  int ans = 0;
  for (int id = 0; id <= lim / B; id++) {
    add(ans, get(id));
  }
  return ans;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) {
    occ[i].push_back(0);
    occ[i].push_back(0);
    vet[i / B].push_back(i);
    psum[i / B].push_back(0);
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    vector<int> &v = occ[a[i]];
    add(v[v.size() - 2] + 1, v.back(), -1);
    add(v.back() + 1, i, +1);
    occ[a[i]].push_back(i);
    dp[i] = query(i);
  }
  cout << dp[n] << endl;
}

```