#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
int a[100003], b[100003], arr[100003];
int dp[100003], res, n, k, x, i;
int main() {
  scanf("%d%d", &n, &k);
  dp[0] = 1;
  for (int j = 1; j <= n; j++) {
    res += dp[j - 1];
    if (res >= 998244353) res -= 998244353;
    scanf("%d", &x);
    for (i = a[x] + 1; i + 2 <= b[x]; i += 3) {
      if (arr[i] == k + 1) {
        res += dp[i - 1];
        if (res >= 998244353) res -= 998244353;
      }
      if (arr[i + 1] == k + 1) {
        res += dp[i];
        if (res >= 998244353) res -= 998244353;
      }
      if (arr[i + 2] == k + 1) {
        res += dp[i + 1];
        if (res >= 998244353) res -= 998244353;
      }
      arr[i]--;
      arr[i + 1]--;
      arr[i + 2]--;
    }
    for (; i <= b[x]; i++) {
      if (arr[i] == k + 1) {
        res += dp[i - 1];
        if (res >= 998244353) res -= 998244353;
      }
      arr[i]--;
    }
    for (i = b[x] + 1; i + 2 <= j; i += 3) {
      if (arr[i] == k) {
        res -= dp[i - 1];
        if (res < 0) res += 998244353;
      }
      if (arr[i + 1] == k) {
        res -= dp[i];
        if (res < 0) res += 998244353;
      }
      if (arr[i + 2] == k) {
        res -= dp[i + 1];
        if (res < 0) res += 998244353;
      }
      arr[i]++;
      arr[i + 1]++;
      arr[i + 2]++;
    }
    for (; i <= j; i++) {
      if (arr[i] == k) {
        res -= dp[i - 1];
        if (res < 0) res += 998244353;
      }
      arr[i]++;
    }
    a[x] = b[x];
    b[x] = j;
    dp[j] = res;
  }
  printf("%d\n", dp[n]);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
int a[100003], b[100003], arr[100003];
int dp[100003], res, n, k, x, i;
int main() {
  scanf("%d%d", &n, &k);
  dp[0] = 1;
  for (int j = 1; j <= n; j++) {
    res += dp[j - 1];
    if (res >= 998244353) res -= 998244353;
    scanf("%d", &x);
    for (i = a[x] + 1; i + 2 <= b[x]; i += 3) {
      if (arr[i] == k + 1) {
        res += dp[i - 1];
        if (res >= 998244353) res -= 998244353;
      }
      if (arr[i + 1] == k + 1) {
        res += dp[i];
        if (res >= 998244353) res -= 998244353;
      }
      if (arr[i + 2] == k + 1) {
        res += dp[i + 1];
        if (res >= 998244353) res -= 998244353;
      }
      arr[i]--;
      arr[i + 1]--;
      arr[i + 2]--;
    }
    for (; i <= b[x]; i++) {
      if (arr[i] == k + 1) {
        res += dp[i - 1];
        if (res >= 998244353) res -= 998244353;
      }
      arr[i]--;
    }
    for (i = b[x] + 1; i + 2 <= j; i += 3) {
      if (arr[i] == k) {
        res -= dp[i - 1];
        if (res < 0) res += 998244353;
      }
      if (arr[i + 1] == k) {
        res -= dp[i];
        if (res < 0) res += 998244353;
      }
      if (arr[i + 2] == k) {
        res -= dp[i + 1];
        if (res < 0) res += 998244353;
      }
      arr[i]++;
      arr[i + 1]++;
      arr[i + 2]++;
    }
    for (; i <= j; i++) {
      if (arr[i] == k) {
        res -= dp[i - 1];
        if (res < 0) res += 998244353;
      }
      arr[i]++;
    }
    a[x] = b[x];
    b[x] = j;
    dp[j] = res;
  }
  printf("%d\n", dp[n]);
  return 0;
}

```