Observations

For a subsequence \(B = (A_{t_1}, \dots, A_{t_k})\) of \(A\), take the lexicographical smallest possible sequence of indices \((t_1, \dots t_k)\). This can be obtained by greedily picking the smallest index \(\displaystyle t'_i = \min_{u > t'_{i-1},\ A_{u} = A_{t_i}} u \) from the first element of \(B\) in order (proof omitted). We call it a greedy index sequence of \(B\).

For a greedy index sequence \(T = (t_1, \dots, t_k)\) of a subsequence that is a 221-sequence, define a sequence of indices \(P = (p_1, \dots, p_m)\) consisting of the positions \(p\) such that “\(p = k\) or (\(p < k\) and \(t_p \neq t_{p+1}\)).” Colloquially, this is “the last index of each block of the greedy index sequence of \(B\).” Then for \(i = 1, \dots, m\) the following holds:

• \(A_{p_{i-1}} \neq A_{p_i}\) (where we define a sentinel \(A_{p_0} := 0\))
• Among the consecutive elements \(A_{p_{i-1} + 1},\ \cdots,\ A_{p_i}\), exactly \(A_{p_i}\) elements are equal to \(A_{p_i}\) (where we define a sentinel \(p_0 := 0\)).

Conversely, for any index sequence \(P\) satisfying the conditions above for all \(i = 1, \dots, |P|\), we can uniquely reconstruct the corresponding \(T\) and thus \(B\). Hence, what we need to count is the number of non-empty index sequences \(P\) satisfying these conditions.

Let \(C_t\) be the number of elements equal to \(A_t\) among \(A_1, \dots, A_{t}\). Also define \(J(x,c)\) as the value satisfying:

• \(A_{J(x,c)} = x\) and \(C_{J(x,c)} = c\) if \(c > 0\);
• \(J(x,c) = -1\) if \(c = 0\).

Then the conditions above for \(i = 1, \dots, |P|\) can be rephrased as follows:

• \(1 \leq p_i \leq N\)
• \(0 \leq C_{p_i} - A_{p_i}\)
• \(J(A_{p_i},\ C_{p_i} - A_{p_i} + 0) < p_{i-1} < J(A_{p_i},\ C_{p_i} - A_{p_i} + 1)\)

The condition above only depends on \(p_{i-1}\), and the values \(p_{i-1}\) satisfying the conditions form a consecutive range.

Define \(dp[p]\) as the number of valid sequences \(P\) that end with \(p\). Consider finding this for \(p = 1, \dots, N\) in order. As a sentinel, define \(dp[0] := 1\).

Then the value \(dp[p]\) equals \(0\) if \(C_{p} - A_p < 0\); otherwise it is obtained as the sum of \(dp[p_{i-1}]\) over \(p_{i-1}\) within the range obtained above. Thus, it is sufficient to compute the values \(A_{p}\) and \(C_p\), and perform element-wise update and segment-sum retrieval.

The values \(A_{p}\) and \(C_p\) can be precomputed in \(O(N)\) time; element-wise update and segment-sum retrieval can be performed in \(O(\log N)\) time per query using a segment tree. (Since update operations occur once each for \(p = 1, \dots, N\) in order, using the cumulative sums allow us to optimize it to a total of \(O(N)\) time.)

The sought answer is the sum of \(dp[1], \dots, dp[N]\), which can be found by implementing the algorithm above.

The time complexity is \(O(N \log N)\) (or \(O(N)\) if you use cumulative sums), which is fast enough in any case.

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <string>
using std::string;
#include <algorithm>
#include <vector>
using std::vector;
#include <queue>
using std::queue;

typedef long long int ll;
const ll FOD = 998244353;

ll n;
vector<ll> a;


void solve () {
	vector<ll> precnt(n);
	vector<vector<ll> > idxs(n+1);

	vector<ll> dp(n);
	vector<ll> acc(n+1);
	acc[0] = 0;

	for (ll i = 0; i < n; i++) {
		precnt[i] = idxs[a[i]].size();
		idxs[a[i]].push_back(i);
	}

	for (ll i = 0; i < n; i++) {
		ll val;
		if (precnt[i] < a[i] - 1) {
			val = 0;
		} else if (precnt[i] == a[i] - 1) {
			// sum[0, idxs[a[i]][precnt[i] - a[i] + 1]) + 1
			val = FOD + acc[idxs[a[i]][precnt[i] - a[i] + 1]] - acc[0];
			val += 1;
		} else {
			// sum(idxs[a[i]][precnt[i] - a[i] + 0],
			//     idxs[a[i]][precnt[i] - a[i] + 1])
			val = FOD
				+ acc[idxs[a[i]][precnt[i] - a[i] + 1]]
				- acc[idxs[a[i]][precnt[i] - a[i] + 0] + 1];
		}
		val %= FOD;
		dp[i] = val;
		acc[i+1] = (acc[i] + dp[i]) % FOD;
	}

	ll ans = 0;
	for (ll i = 0; i < n; i++) {
		ans += dp[i];
	}
	ans %= FOD;
	cout << ans << "\n";
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	solve();

	return 0;
}