Submission #47990255

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e5 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n;
int a[N], cnt[N], f[N], d[N];
int solve(int l, int r) {
  for(int i = l; i <= r; i++)a[i - l + 1] = a[i];
  int n = r - l + 1, col = 0, j = 1;
  for(int i = 1; i <= n; i++)f[i] = d[i] = 0;
  f[1] = 1;
  for(int i = 1; i <= n; i++) {
    add(d[i], d[i - 1]); add(f[i], d[i]);
    while(j <= n && col <= 2)col += !cnt[a[j]], cnt[a[j]]++, j++;
    if(col > 2)add(d[j - 1], f[i]);
    if(i < n)add(f[i + 1], f[i]);
    if(i + 2 <= n && a[i + 2] == a[i])add(f[i + 2], f[i]);
    cnt[a[i]]--; col -= !cnt[a[i]];
  }
  return f[n];
}
int main() {
  n = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  int ans = 1;
  for(int i = 1; i <= n; i++) {
    int k = i;
    while(k < n && a[k + 1] != a[k])k++;
    ans = 1ll * ans * solve(i, k) % P; i = k;
  }
  printf("%d\n", ans);
  return 0;
}

Submission Info

Judge Result