#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAX_N = 2e5 + 5;
vector<int> occurrences[MAX_N];
int cnt[MAX_N], dp[MAX_N];
void add_self(int& a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}
const int B = 256;
struct Bucket {
  int id;
  int offset;
  int pref_sum[B];
  void rebuild() {
    int first = id * B, last = (id + 1) * B - 1;
    int smallest = INT_MAX;
    for (int i = first; i <= last; ++i) {
      smallest = min(smallest, offset + cnt[i]);
    }
    for (int i = first; i <= last; ++i) {
      cnt[i] -= smallest - offset;
      assert(0 <= cnt[i] && cnt[i] < B);
    }
    offset = smallest;
    for (int x = 0; x < B; ++x) {
      pref_sum[x] = 0;
    }
    for (int i = first; i <= last; ++i) {
      add_self(pref_sum[cnt[i]], dp[i]);
    }
    for (int x = 1; x < B; ++x) {
      add_self(pref_sum[x], pref_sum[x - 1]);
    }
  }
} buckets[MAX_N / B + 1];
int which(int i) { return i / B; }
void add(int a, int b, int diff) {
  for (int i = a; i <= b && which(i) == which(a); ++i) {
    cnt[i] += diff;
  }
  buckets[which(a)].rebuild();
  if (which(a) == which(b)) {
    return;
  }
  for (int i = which(a) + 1; i < which(b); ++i) {
    buckets[i].offset += diff;
  }
  for (int i = b; which(i) == which(b); --i) {
    cnt[i] += diff;
  }
  buckets[which(b)].rebuild();
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i <= which(n - 1); ++i) {
    buckets[i].id = i;
  }
  for (int x = 1; x <= n; ++x) {
    occurrences[x].push_back(-1);
  }
  dp[0] = 1;
  buckets[which(0)].rebuild();
  for (int R = 0; R < n; ++R) {
    int x;
    scanf("%d", &x);
    vector<int>& vec = occurrences[x];
    if ((int)vec.size() >= 2) {
      add(vec.end()[-2] + 1, vec.back(), -1);
    }
    add(vec.back() + 1, R, 1);
    vec.push_back(R);
    int total = 0;
    for (int i = 0; i <= which(R); ++i) {
      int at_most = k - buckets[i].offset;
      if (at_most >= 0) {
        add_self(total, buckets[i].pref_sum[min(at_most, B - 1)]);
      }
    }
    dp[R + 1] = total;
    buckets[which(R + 1)].rebuild();
  }
  printf("%d\n", dp[n]);
}

### 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>
using namespace std;
const int mod = 998244353;
const int MAX_N = 2e5 + 5;
vector<int> occurrences[MAX_N];
int cnt[MAX_N], dp[MAX_N];
void add_self(int& a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}
const int B = 256;
struct Bucket {
  int id;
  int offset;
  int pref_sum[B];
  void rebuild() {
    int first = id * B, last = (id + 1) * B - 1;
    int smallest = INT_MAX;
    for (int i = first; i <= last; ++i) {
      smallest = min(smallest, offset + cnt[i]);
    }
    for (int i = first; i <= last; ++i) {
      cnt[i] -= smallest - offset;
      assert(0 <= cnt[i] && cnt[i] < B);
    }
    offset = smallest;
    for (int x = 0; x < B; ++x) {
      pref_sum[x] = 0;
    }
    for (int i = first; i <= last; ++i) {
      add_self(pref_sum[cnt[i]], dp[i]);
    }
    for (int x = 1; x < B; ++x) {
      add_self(pref_sum[x], pref_sum[x - 1]);
    }
  }
} buckets[MAX_N / B + 1];
int which(int i) { return i / B; }
void add(int a, int b, int diff) {
  for (int i = a; i <= b && which(i) == which(a); ++i) {
    cnt[i] += diff;
  }
  buckets[which(a)].rebuild();
  if (which(a) == which(b)) {
    return;
  }
  for (int i = which(a) + 1; i < which(b); ++i) {
    buckets[i].offset += diff;
  }
  for (int i = b; which(i) == which(b); --i) {
    cnt[i] += diff;
  }
  buckets[which(b)].rebuild();
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i <= which(n - 1); ++i) {
    buckets[i].id = i;
  }
  for (int x = 1; x <= n; ++x) {
    occurrences[x].push_back(-1);
  }
  dp[0] = 1;
  buckets[which(0)].rebuild();
  for (int R = 0; R < n; ++R) {
    int x;
    scanf("%d", &x);
    vector<int>& vec = occurrences[x];
    if ((int)vec.size() >= 2) {
      add(vec.end()[-2] + 1, vec.back(), -1);
    }
    add(vec.back() + 1, R, 1);
    vec.push_back(R);
    int total = 0;
    for (int i = 0; i <= which(R); ++i) {
      int at_most = k - buckets[i].offset;
      if (at_most >= 0) {
        add_self(total, buckets[i].pref_sum[min(at_most, B - 1)]);
      }
    }
    dp[R + 1] = total;
    buckets[which(R + 1)].rebuild();
  }
  printf("%d\n", dp[n]);
}

```