这说明你的能力还不足以维持 IM。
显然 balanced 的充要条件是，对于每个值，染色一定是 RB 交替。然后一种值只会有先染红或先染蓝两种情况。
然后还剩下字典序严格小于的条件。我场上的想法是枚举 \(\text{LCP}\)，然后推出来一个巨大麻烦做法，根本写不出来。
但是实际上字典序严格小于就是诈骗。考虑遇到第一个红蓝组成的子序列不等的值，此时我们存在唯一一种是否交换这两种颜色的方案，使得红子序列字典序严格小于（或大于）蓝子序列。
所以，如果设 \(a\) 为红小于蓝的方案数，\(b\) 为红大于蓝的方案数，\(c\) 为红等于蓝的方案数（这里均指字典序），\(k\) 为序列中出现的不同的值的个数，那么有 \(a = b, a + b + c = 2^k\)，所以 \(a = b = \frac{2^k - c}{2}\)。问题来到如何求 \(c\)。
既然红等于蓝，那么如果有一种值出现奇数次就寄了。
然后我们考虑把每种值第奇数次出现和第偶数次出现的位置连起来，这样组成了若干条线段，并且线段的左端点和右端点染的颜色一定不同。
若线段存在包含关系，那么一定不能做到字典序相等。
否则，对于一对相交的线段，一定是形如 \(l_1 < l_2 < r_1 < r_2\) 的形式，那么由字典序相等的限制，可知此时 \(l_2\) 位置的颜色和 \(l_1\) 位置的颜色相等。那么最后我们会得到若干个等价类，设等价类的个数为 \(d\)，那么 \(c = 2^d\)。
时间复杂度 \(O(n \log n)\)。
code
// Problem: D. Lexichromatography
// Contest: Codeforces - Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
// URL: https://codeforces.com/contest/1876/problem/D
// Memory Limit: 512 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 mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
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], pw[maxn], fa[maxn];
vector<int> vc[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
return 1;
} else {
return 0;
}
}
void solve() {
scanf("%lld", &n);
ll N = 0;
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
N = max(N, a[i]);
vc[a[i]].pb(i);
pw[i] = pw[i - 1] * 2 % mod;
}
int cnt = 0;
for (int i = 1; i <= N; ++i) {
fa[i] = i;
if (vc[i].size()) {
++cnt;
}
}
for (int i = 1; i <= N; ++i) {
if (vc[i].size() & 1) {
printf("%lld\n", pw[cnt - 1]);
return;
}
}
vector<pii> S;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < (int)vc[i].size(); j += 2) {
S.pb(vc[i][j], vc[i][j + 1]);
}
}
sort(S.begin(), S.end());
for (int i = 1; i < (int)S.size(); ++i) {
if (S[i].scd < S[i - 1].scd) {
printf("%lld\n", pw[cnt - 1]);
return;
}
}
int lst = 0, t = cnt;
for (pii p : S) {
int l = p.fst, r = p.scd;
if (l < lst) {
if (merge(a[l], a[lst])) {
--t;
}
}
lst = r;
}
printf("%lld\n", (pw[cnt - 1] - pw[t - 1] + mod) % mod);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}