#include <bits/stdc++.h>
using namespace std;
const int MX_N = 1e5 + 5;
const int MX_K = 1e5 + 5;
const int MX_A = MX_N;
const int MOD = 998244353;
const int B = 300;
int N, K, A[MX_N];
int pos[MX_A], prv[MX_N], dp[MX_N];
struct Bucket {
  int pre[B], cnt[B], offset;
  Bucket() {
    for (int i = (0); i <= (B - 1); ++i) {
      pre[i] = 0;
      cnt[i] = 0;
    }
    offset = 0;
  }
  void rebuild(int b) {
    int mn = MX_N;
    int j = b * B;
    for (int i = (0); i <= (B - 1); ++i) {
      pre[i] = 0;
      mn = min(mn, cnt[i]);
    }
    offset += mn;
    for (int i = (0); i <= (B - 1); ++i) {
      cnt[i] -= mn;
      pre[cnt[i]] += dp[i + j];
      if (pre[cnt[i]] >= MOD) pre[cnt[i]] -= MOD;
    }
    for (int i = (1); i <= (B - 1); ++i) {
      pre[i] += pre[i - 1];
      if (pre[i] >= MOD) pre[i] -= MOD;
    }
  }
  int sum() {
    if (offset > K) return 0;
    return pre[min(B - 1, K - offset)];
  }
  int get(int b, int i) {
    if (offset + cnt[i] > K) return 0;
    return dp[b * B + i];
  }
} bucket[MX_N / B + 1];
void update(int x, int y, int v) {
  if (x > y) return;
  int bx = x / B, jx = x % B, by = y / B, jy = y % B;
  if (bx == by) {
    for (int i = (jx); i <= (jy); ++i) {
      bucket[bx].cnt[i] += v;
    }
    bucket[bx].rebuild(bx);
  } else {
    for (int i = (jx); i <= (B - 1); ++i) {
      bucket[bx].cnt[i] += v;
    }
    bucket[bx].rebuild(bx);
    for (int i = (bx + 1); i <= (by - 1); ++i) {
      bucket[i].offset += v;
    }
    for (int i = (0); i <= (jy); ++i) {
      bucket[by].cnt[i] += v;
    }
    bucket[by].rebuild(by);
  }
}
int query(int i) {
  int b = i / B, j = i % B;
  int sum = 0;
  for (int k = (0); k <= (b - 1); ++k) {
    sum += bucket[k].sum();
    if (sum >= MOD) sum -= MOD;
  }
  for (int k = (0); k <= (j); ++k) {
    sum += bucket[b].get(b, k);
    if (sum >= MOD) sum -= MOD;
  }
  return sum;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> K;
  for (int i = (1); i <= (N); ++i) {
    cin >> A[i];
    prv[i] = pos[A[i]];
    pos[A[i]] = i;
  }
  dp[0] = 1;
  bucket[0].rebuild(0);
  for (int i = (1); i <= (N); ++i) {
    update(prv[prv[i]], prv[i] - 1, -1);
    update(prv[i], i - 1, 1);
    dp[i] = query(i - 1);
    int b = i / B;
    bucket[b].rebuild(b);
  }
  cout << dp[N];
}

### 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 MX_N = 1e5 + 5;
const int MX_K = 1e5 + 5;
const int MX_A = MX_N;
const int MOD = 998244353;
const int B = 300;
int N, K, A[MX_N];
int pos[MX_A], prv[MX_N], dp[MX_N];
struct Bucket {
  int pre[B], cnt[B], offset;
  Bucket() {
    for (int i = (0); i <= (B - 1); ++i) {
      pre[i] = 0;
      cnt[i] = 0;
    }
    offset = 0;
  }
  void rebuild(int b) {
    int mn = MX_N;
    int j = b * B;
    for (int i = (0); i <= (B - 1); ++i) {
      pre[i] = 0;
      mn = min(mn, cnt[i]);
    }
    offset += mn;
    for (int i = (0); i <= (B - 1); ++i) {
      cnt[i] -= mn;
      pre[cnt[i]] += dp[i + j];
      if (pre[cnt[i]] >= MOD) pre[cnt[i]] -= MOD;
    }
    for (int i = (1); i <= (B - 1); ++i) {
      pre[i] += pre[i - 1];
      if (pre[i] >= MOD) pre[i] -= MOD;
    }
  }
  int sum() {
    if (offset > K) return 0;
    return pre[min(B - 1, K - offset)];
  }
  int get(int b, int i) {
    if (offset + cnt[i] > K) return 0;
    return dp[b * B + i];
  }
} bucket[MX_N / B + 1];
void update(int x, int y, int v) {
  if (x > y) return;
  int bx = x / B, jx = x % B, by = y / B, jy = y % B;
  if (bx == by) {
    for (int i = (jx); i <= (jy); ++i) {
      bucket[bx].cnt[i] += v;
    }
    bucket[bx].rebuild(bx);
  } else {
    for (int i = (jx); i <= (B - 1); ++i) {
      bucket[bx].cnt[i] += v;
    }
    bucket[bx].rebuild(bx);
    for (int i = (bx + 1); i <= (by - 1); ++i) {
      bucket[i].offset += v;
    }
    for (int i = (0); i <= (jy); ++i) {
      bucket[by].cnt[i] += v;
    }
    bucket[by].rebuild(by);
  }
}
int query(int i) {
  int b = i / B, j = i % B;
  int sum = 0;
  for (int k = (0); k <= (b - 1); ++k) {
    sum += bucket[k].sum();
    if (sum >= MOD) sum -= MOD;
  }
  for (int k = (0); k <= (j); ++k) {
    sum += bucket[b].get(b, k);
    if (sum >= MOD) sum -= MOD;
  }
  return sum;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> K;
  for (int i = (1); i <= (N); ++i) {
    cin >> A[i];
    prv[i] = pos[A[i]];
    pos[A[i]] = i;
  }
  dp[0] = 1;
  bucket[0].rebuild(0);
  for (int i = (1); i <= (N); ++i) {
    update(prv[prv[i]], prv[i] - 1, -1);
    update(prv[i], i - 1, 1);
    dp[i] = query(i - 1);
    int b = i / B;
    bucket[b].rebuild(b);
  }
  cout << dp[N];
}

```