#include <bits/stdc++.h>
using namespace std;
const int BASE = 998244353;
const int SZ = 320;
struct BlockData {
  int sumC;
  vector<long long> sumF;
  BlockData() {}
};
int n, k, c[100100];
long long f[100100];
BlockData blocks[SZ];
long long calc(int i) {
  long long res = 0;
  int sumC = 0, block = i / SZ;
  for (int j = i; j >= block * SZ; j--) {
    sumC += c[j];
    if (sumC <= k) res += j ? f[j - 1] : 1;
  }
  for (int j = block - 1; j >= 0; j--) {
    int need = k - sumC;
    if (need >= -SZ) res += blocks[j].sumF[min(need, SZ) + SZ];
    sumC += blocks[j].sumC;
  }
  return res % BASE;
}
void constructBlock(int block) {
  BlockData &data = blocks[block];
  data.sumC = 0;
  data.sumF = vector<long long>(SZ * 2 + 1, 0);
  for (int i = block * SZ + SZ - 1; i >= block * SZ; i--) {
    data.sumC += c[i];
    data.sumF[data.sumC + SZ] += i ? f[i - 1] : 1;
  }
  for (int i = 0; i <= SZ * 2; i++) {
    if (i) data.sumF[i] += data.sumF[i - 1];
    data.sumF[i] %= BASE;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int x;
  cin >> n >> k;
  vector<int> id[100100];
  for (int i = 0; i < n; i++) {
    cin >> x;
    c[i] = 1;
    if (!id[x].empty()) {
      int j = id[x].back();
      c[j] = -1;
      if (id[x].size() >= 2) {
        int k = id[x][id[x].size() - 2];
        c[k] = 0;
        if (k / SZ != j / SZ) constructBlock(k / SZ);
      }
      if (j / SZ != i / SZ) constructBlock(j / SZ);
    }
    id[x].push_back(i);
    f[i] = calc(i);
    if (i % SZ == SZ - 1) constructBlock(i / SZ);
  }
  cout << f[n - 1] << 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 int BASE = 998244353;
const int SZ = 320;
struct BlockData {
  int sumC;
  vector<long long> sumF;
  BlockData() {}
};
int n, k, c[100100];
long long f[100100];
BlockData blocks[SZ];
long long calc(int i) {
  long long res = 0;
  int sumC = 0, block = i / SZ;
  for (int j = i; j >= block * SZ; j--) {
    sumC += c[j];
    if (sumC <= k) res += j ? f[j - 1] : 1;
  }
  for (int j = block - 1; j >= 0; j--) {
    int need = k - sumC;
    if (need >= -SZ) res += blocks[j].sumF[min(need, SZ) + SZ];
    sumC += blocks[j].sumC;
  }
  return res % BASE;
}
void constructBlock(int block) {
  BlockData &data = blocks[block];
  data.sumC = 0;
  data.sumF = vector<long long>(SZ * 2 + 1, 0);
  for (int i = block * SZ + SZ - 1; i >= block * SZ; i--) {
    data.sumC += c[i];
    data.sumF[data.sumC + SZ] += i ? f[i - 1] : 1;
  }
  for (int i = 0; i <= SZ * 2; i++) {
    if (i) data.sumF[i] += data.sumF[i - 1];
    data.sumF[i] %= BASE;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int x;
  cin >> n >> k;
  vector<int> id[100100];
  for (int i = 0; i < n; i++) {
    cin >> x;
    c[i] = 1;
    if (!id[x].empty()) {
      int j = id[x].back();
      c[j] = -1;
      if (id[x].size() >= 2) {
        int k = id[x][id[x].size() - 2];
        c[k] = 0;
        if (k / SZ != j / SZ) constructBlock(k / SZ);
      }
      if (j / SZ != i / SZ) constructBlock(j / SZ);
    }
    id[x].push_back(i);
    f[i] = calc(i);
    if (i % SZ == SZ - 1) constructBlock(i / SZ);
  }
  cout << f[n - 1] << endl;
}

```