#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
using namespace std;
using ll = long long;
int a[101001];
int b[101010];
int dp[101010];
int p1[101010];
int p2[101010];
ll ans = 0;
int n, k;
void add(int* __restrict a, int* __restrict dp, int n) {
  for (int i = 0; i < n; ++i) {
    a[i]++;
    ans -= a[i] == 0 ? dp[i] : 0;
  }
}
void sub(int* __restrict a, int* __restrict dp, int n) {
  for (int i = 0; i < n; ++i) {
    ans += a[i] == 0 ? dp[i] : 0;
    a[i]--;
  }
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    b[i] = -k - 1;
    cin >> a[i];
    --a[i];
    p1[i] = p2[i] = -1;
  }
  dp[0] = 1;
  ans = 1;
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    sub(b + p2[x] + 1, dp + p2[x] + 1, p1[x] - p2[x]);
    add(b + p1[x] + 1, dp + p1[x] + 1, i - p1[x]);
    ans %= 998244353;
    if (ans < 0) ans += 998244353;
    dp[i + 1] = (int)ans;
    ans *= 2;
    p2[x] = p1[x];
    p1[x] = i;
  }
  cout << ans / 2 << endl;
  return 0;
}

### Prompt

Generate 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
using namespace std;
using ll = long long;
int a[101001];
int b[101010];
int dp[101010];
int p1[101010];
int p2[101010];
ll ans = 0;
int n, k;
void add(int* __restrict a, int* __restrict dp, int n) {
  for (int i = 0; i < n; ++i) {
    a[i]++;
    ans -= a[i] == 0 ? dp[i] : 0;
  }
}
void sub(int* __restrict a, int* __restrict dp, int n) {
  for (int i = 0; i < n; ++i) {
    ans += a[i] == 0 ? dp[i] : 0;
    a[i]--;
  }
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    b[i] = -k - 1;
    cin >> a[i];
    --a[i];
    p1[i] = p2[i] = -1;
  }
  dp[0] = 1;
  ans = 1;
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    sub(b + p2[x] + 1, dp + p2[x] + 1, p1[x] - p2[x]);
    add(b + p1[x] + 1, dp + p1[x] + 1, i - p1[x]);
    ans %= 998244353;
    if (ans < 0) ans += 998244353;
    dp[i + 1] = (int)ans;
    ans *= 2;
    p2[x] = p1[x];
    p1[x] = i;
  }
  cout << ans / 2 << endl;
  return 0;
}

```