#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int SZ = 320;
const long long MOD = 998244353;
int N, K;
int prv[MAX_N + 1];
int arr[MAX_N + 1];
int pidx[MAX_N + 1];
int num[MAX_N + 1];
long long dp[MAX_N + 1];
long long dp2[SZ + 1][MAX_N + 1];
long long D;
int add[SZ + 1];
void Update(int x, int y, int z) {
  for (int i = 0; i < SZ; i++) {
    int s = i * SZ, e = min(N, (i + 1) * SZ - 1);
    if (s > e) return;
    if (x <= s && e <= y) {
      if (z == 1) {
        add[i]++;
        if (K + 1 - add[i] >= 0 && K + 1 - add[i] <= N) {
          D = (D - dp2[i][K + 1 - add[i]] + MOD) % MOD;
        }
      } else {
        add[i]--;
        if (K - add[i] >= 0 && K - add[i] <= N) {
          D = (D + dp2[i][K - add[i]]) % MOD;
        }
      }
    } else if (x > e || y < s)
      continue;
    else {
      for (int j = s; j <= e; j++) {
        dp2[i][num[j]] = 0LL;
        num[j] += add[i];
      }
      add[i] = 0LL;
      for (int j = max(s, x); j <= min(e, y); j++) {
        num[j] += z;
        if (z == 1) {
          if (num[j] == K + 1) {
            D = (D - dp[j] + MOD) % MOD;
          }
        } else {
          if (num[j] == K) {
            D = (D + dp[j]) % MOD;
          }
        }
      }
      for (int j = s; j <= e; j++) {
        dp2[i][num[j]] = (dp2[i][num[j]] + dp[j]) % MOD;
      }
    }
  }
}
void Add(int x) {
  int g = x / SZ;
  int s = g * SZ;
  for (int i = s; i < x; i++) {
    dp2[g][num[i]] = 0LL;
    num[i] += add[g];
  }
  add[g] = 0;
  for (int i = s; i <= x; i++) {
    dp2[g][num[i]] = (dp2[g][num[i]] + dp[i]) % MOD;
  }
  D = (D + dp[x]) % MOD;
}
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
    prv[i] = pidx[arr[i]];
    pidx[arr[i]] = i;
  }
  dp[0] = 1;
  D = 1LL;
  for (int i = 1; i <= N; i++) {
    Update(prv[i], i - 1, 1);
    if (prv[i] != 0) {
      Update(prv[prv[i]], prv[i] - 1, -1);
    }
    dp[i] = D;
    Add(i);
  }
  cout << dp[N];
  return 0;
}

### 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 MAX_N = 100000;
const int SZ = 320;
const long long MOD = 998244353;
int N, K;
int prv[MAX_N + 1];
int arr[MAX_N + 1];
int pidx[MAX_N + 1];
int num[MAX_N + 1];
long long dp[MAX_N + 1];
long long dp2[SZ + 1][MAX_N + 1];
long long D;
int add[SZ + 1];
void Update(int x, int y, int z) {
  for (int i = 0; i < SZ; i++) {
    int s = i * SZ, e = min(N, (i + 1) * SZ - 1);
    if (s > e) return;
    if (x <= s && e <= y) {
      if (z == 1) {
        add[i]++;
        if (K + 1 - add[i] >= 0 && K + 1 - add[i] <= N) {
          D = (D - dp2[i][K + 1 - add[i]] + MOD) % MOD;
        }
      } else {
        add[i]--;
        if (K - add[i] >= 0 && K - add[i] <= N) {
          D = (D + dp2[i][K - add[i]]) % MOD;
        }
      }
    } else if (x > e || y < s)
      continue;
    else {
      for (int j = s; j <= e; j++) {
        dp2[i][num[j]] = 0LL;
        num[j] += add[i];
      }
      add[i] = 0LL;
      for (int j = max(s, x); j <= min(e, y); j++) {
        num[j] += z;
        if (z == 1) {
          if (num[j] == K + 1) {
            D = (D - dp[j] + MOD) % MOD;
          }
        } else {
          if (num[j] == K) {
            D = (D + dp[j]) % MOD;
          }
        }
      }
      for (int j = s; j <= e; j++) {
        dp2[i][num[j]] = (dp2[i][num[j]] + dp[j]) % MOD;
      }
    }
  }
}
void Add(int x) {
  int g = x / SZ;
  int s = g * SZ;
  for (int i = s; i < x; i++) {
    dp2[g][num[i]] = 0LL;
    num[i] += add[g];
  }
  add[g] = 0;
  for (int i = s; i <= x; i++) {
    dp2[g][num[i]] = (dp2[g][num[i]] + dp[i]) % MOD;
  }
  D = (D + dp[x]) % MOD;
}
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
    prv[i] = pidx[arr[i]];
    pidx[arr[i]] = i;
  }
  dp[0] = 1;
  D = 1LL;
  for (int i = 1; i <= N; i++) {
    Update(prv[i], i - 1, 1);
    if (prv[i] != 0) {
      Update(prv[prv[i]], prv[i] - 1, -1);
    }
    dp[i] = D;
    Add(i);
  }
  cout << dp[N];
  return 0;
}

```