#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAXN = 2e5;
const int B = 315;
int cnt[MAXN], dp[MAXN];
vector<int> occ[MAXN];
void add_self(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void min_self(int &x, int y) { x = min(x, y); }
struct SQRT {
  int id, offset, pref_sum[B];
  void rebuild() {
    int st = id * B, dr = (id + 1) * B - 1, minn = INT_MAX;
    for (int i = st; i <= dr; ++i) min_self(minn, offset + cnt[i]);
    for (int i = st; i <= dr; ++i) cnt[i] -= minn - offset;
    offset = minn;
    for (int i = 0; i < B; ++i) pref_sum[i] = 0;
    for (int i = st; i <= dr; ++i) add_self(pref_sum[cnt[i]], dp[i]);
    for (int i = 1; i < B; ++i) add_self(pref_sum[i], pref_sum[i - 1]);
  }
} a[MAXN / B + 1];
int get_bucket(int index) { return index / B; }
void update(int l, int r, short t) {
  int bl = get_bucket(l), br = get_bucket(r);
  for (int i = l; i <= r && get_bucket(i) == bl; ++i) cnt[i] += t;
  a[bl].rebuild();
  if (bl == br) return;
  for (int i = bl + 1; i < br; ++i) a[i].offset += t;
  for (int i = r; get_bucket(i) == br; --i) cnt[i] += t;
  a[br].rebuild();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i <= get_bucket(n); ++i) a[i].id = i;
  for (int i = 1; i <= n; ++i) occ[i].emplace_back(-1);
  dp[0] = 1;
  a[0].rebuild();
  for (int r = 0; r < n; ++r) {
    int x;
    cin >> x;
    vector<int> &vec = occ[x];
    if (static_cast<int>(vec.size()) >= 2)
      update(vec.end()[-2] + 1, vec.back(), -1);
    update(vec.back() + 1, r, 1);
    vec.emplace_back(r);
    int val = 0;
    for (int i = 0; i <= get_bucket(r); ++i) {
      int at_most = k - a[i].offset;
      if (at_most >= 0) add_self(val, a[i].pref_sum[min(at_most, B - 1)]);
    }
    dp[r + 1] = val;
    a[get_bucket(r + 1)].rebuild();
  }
  cout << dp[n] << '\n';
  return 0;
}

### Prompt

Please formulate 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 MAXN = 2e5;
const int B = 315;
int cnt[MAXN], dp[MAXN];
vector<int> occ[MAXN];
void add_self(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void min_self(int &x, int y) { x = min(x, y); }
struct SQRT {
  int id, offset, pref_sum[B];
  void rebuild() {
    int st = id * B, dr = (id + 1) * B - 1, minn = INT_MAX;
    for (int i = st; i <= dr; ++i) min_self(minn, offset + cnt[i]);
    for (int i = st; i <= dr; ++i) cnt[i] -= minn - offset;
    offset = minn;
    for (int i = 0; i < B; ++i) pref_sum[i] = 0;
    for (int i = st; i <= dr; ++i) add_self(pref_sum[cnt[i]], dp[i]);
    for (int i = 1; i < B; ++i) add_self(pref_sum[i], pref_sum[i - 1]);
  }
} a[MAXN / B + 1];
int get_bucket(int index) { return index / B; }
void update(int l, int r, short t) {
  int bl = get_bucket(l), br = get_bucket(r);
  for (int i = l; i <= r && get_bucket(i) == bl; ++i) cnt[i] += t;
  a[bl].rebuild();
  if (bl == br) return;
  for (int i = bl + 1; i < br; ++i) a[i].offset += t;
  for (int i = r; get_bucket(i) == br; --i) cnt[i] += t;
  a[br].rebuild();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i <= get_bucket(n); ++i) a[i].id = i;
  for (int i = 1; i <= n; ++i) occ[i].emplace_back(-1);
  dp[0] = 1;
  a[0].rebuild();
  for (int r = 0; r < n; ++r) {
    int x;
    cin >> x;
    vector<int> &vec = occ[x];
    if (static_cast<int>(vec.size()) >= 2)
      update(vec.end()[-2] + 1, vec.back(), -1);
    update(vec.back() + 1, r, 1);
    vec.emplace_back(r);
    int val = 0;
    for (int i = 0; i <= get_bucket(r); ++i) {
      int at_most = k - a[i].offset;
      if (at_most >= 0) add_self(val, a[i].pref_sum[min(at_most, B - 1)]);
    }
    dp[r + 1] = val;
    a[get_bucket(r + 1)].rebuild();
  }
  cout << dp[n] << '\n';
  return 0;
}

```