考虑把所有 \(a_i = a_{i+1}\) 的位置断开，分别计算然后把方案数乘起来。接下来的讨论假设 \(a_i \ne a_{i+1}\)。
考虑一个 dp，设 \(f_i\) 为 \([1,i]\) 最后剩下的集合的方案数。转移显然是 \(f_i \gets f_i + f_j\)，但是需要满足 \((a_j, a_{j+1}, ..., a_i)\) 需要被删至只剩 \((a_j, a_i)\)。
现在问题变成了如何判定 \((a_1, a_2, ..., a_m)\) 可以被删至只剩 \((a_1, a_m)\)。
如果 \(m \le 3\) 一定可行，下面假设 \(m \ge 4\)。
发现只要数组中不同数的个数 \(\ge 3\) 即可。
考虑证明。如果不同数的个数 \(\le 2\) 一定不可行，否则接下来找到 \(a_{i-1}, a_i, a_{i+1}\) 使得它们两两互不相同，如果删去 \(a_i\) 后不同数个数变成 \(2\)，那么数组形式一定是 \((x,y,...,x,y,a_i,x,y,...)\)。此时删去 \(a_{i-1}\) 或 \(a_{i+1}\) 即可。否则删去 \(a_i\)。证毕。
知道了这个限制，可以双指针 + 前缀和简单维护。
时间复杂度 \(O(n)\)。
code
// Problem: D - Neq Neq
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128）
// URL: https://atcoder.jp/contests/arc128/tasks/arc128_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
ll n, a[maxn], f[maxn], g[maxn], b[maxn], c[maxn], cnt, m;
inline void add(ll x) {
cnt += (!c[x]);
++c[x];
}
inline void del(ll x) {
--c[x];
cnt -= (!c[x]);
}
inline ll calc() {
for (int i = 1, j = 0; i <= m; ++i) {
f[i] = (i == 1);
if (i > 1) {
f[i] = (f[i] + f[i - 1]) % mod;
}
if (i > 2) {
f[i] = (f[i] + f[i - 2]) % mod;
}
add(b[i]);
while (cnt >= 3) {
del(b[++j]);
}
f[i] = (f[i] + g[min(j, max(i - 3, 0))]) % mod;
g[i] = (g[i - 1] + f[i]) % mod;
}
return f[m];
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
ll ans = 1;
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && a[j] != a[j + 1]) {
++j;
}
m = 0;
for (int k = i; k <= j; ++k) {
b[++m] = a[k];
}
ans = ans * calc() % mod;
cnt = 0;
for (int k = i; k <= j; ++k) {
c[a[k]] = 0;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}