#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int b = 325;
int dp[100005];
int a[100005], cnt[100005];
int s[100005], e[100005];
vector<int> v[100005];
struct bucket {
  int val[2 * b + 5];
  int sum = 0;
  void rebuild(int s, int e) {
    for (int i = 0; i <= 2 * b; i++) val[i] = 0;
    sum = 0;
    for (int i = e; i >= s; i--) {
      sum += cnt[i];
      val[b + sum] = (val[b + sum] + dp[i - 1]) % mod;
    }
    for (int i = 1; i <= 2 * b; i++) val[i] = (val[i] + val[i - 1]) % mod;
  }
} bucket[b + 5];
int main() {
  int n, k, a;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int bi = i / b;
    e[bi] = i;
    if (s[bi] == 0) s[bi] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a);
    if (v[a].size() >= 1) {
      cnt[v[a][v[a].size() - 1]] = -1;
      int idx = (v[a][v[a].size() - 1]) / b;
      bucket[idx].rebuild(s[idx], e[idx]);
      if (v[a].size() >= 2) {
        cnt[v[a][v[a].size() - 2]] = 0;
        int idx = (v[a][v[a].size() - 2]) / b;
        bucket[idx].rebuild(s[idx], e[idx]);
      }
    }
    v[a].push_back(i);
    cnt[i] = 1;
    int idx = i / b;
    bucket[idx].rebuild(s[idx], e[idx]);
    int l = 1, r = i;
    int bl = l / b, br = r / b;
    if (bl == br) {
      int sum = 0;
      for (int j = r; j >= l; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
    } else {
      int sum = 0;
      for (int j = r; j >= s[br]; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
      for (int j = br - 1; j >= bl + 1; j--) {
        int d = min(2 * b, k - sum + b);
        if (d >= 0) dp[i] = (dp[i] + bucket[j].val[d]) % mod;
        sum += bucket[j].sum;
      }
      for (int j = e[bl]; j >= l; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
    }
  }
  printf("%d\n", dp[n]);
}

### Prompt

Create a solution in cpp for 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 b = 325;
int dp[100005];
int a[100005], cnt[100005];
int s[100005], e[100005];
vector<int> v[100005];
struct bucket {
  int val[2 * b + 5];
  int sum = 0;
  void rebuild(int s, int e) {
    for (int i = 0; i <= 2 * b; i++) val[i] = 0;
    sum = 0;
    for (int i = e; i >= s; i--) {
      sum += cnt[i];
      val[b + sum] = (val[b + sum] + dp[i - 1]) % mod;
    }
    for (int i = 1; i <= 2 * b; i++) val[i] = (val[i] + val[i - 1]) % mod;
  }
} bucket[b + 5];
int main() {
  int n, k, a;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int bi = i / b;
    e[bi] = i;
    if (s[bi] == 0) s[bi] = i;
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a);
    if (v[a].size() >= 1) {
      cnt[v[a][v[a].size() - 1]] = -1;
      int idx = (v[a][v[a].size() - 1]) / b;
      bucket[idx].rebuild(s[idx], e[idx]);
      if (v[a].size() >= 2) {
        cnt[v[a][v[a].size() - 2]] = 0;
        int idx = (v[a][v[a].size() - 2]) / b;
        bucket[idx].rebuild(s[idx], e[idx]);
      }
    }
    v[a].push_back(i);
    cnt[i] = 1;
    int idx = i / b;
    bucket[idx].rebuild(s[idx], e[idx]);
    int l = 1, r = i;
    int bl = l / b, br = r / b;
    if (bl == br) {
      int sum = 0;
      for (int j = r; j >= l; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
    } else {
      int sum = 0;
      for (int j = r; j >= s[br]; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
      for (int j = br - 1; j >= bl + 1; j--) {
        int d = min(2 * b, k - sum + b);
        if (d >= 0) dp[i] = (dp[i] + bucket[j].val[d]) % mod;
        sum += bucket[j].sum;
      }
      for (int j = e[bl]; j >= l; j--) {
        sum += cnt[j];
        if (sum <= k) dp[i] = (dp[i] + dp[j - 1]) % mod;
      }
    }
  }
  printf("%d\n", dp[n]);
}

```