考察

\(A\) の任意の部分列 \(B = (A_{t_1}, \dots, A_{t_k})\) について，その添字列 \((t_1, \dots t_k)\) としてあり得る辞書順最小のものをとります．これは，\(B\) の先頭要素から順に，添字を貪欲に最小化したもの \(\displaystyle t'_i = \min_{u > t'_{i-1},\ A_{u} = A_{t_i}} u \) に一致します(証明略)．これを \(B\) の貪欲な添字列と呼ぶことにします．

221 数列であるような部分列に対応する貪欲な添字列 \(T = (t_1, \dots, t_k)\) について，「\(p = k\) または (\(p < k\) かつ \(A_{t_p} \neq A_{t_{p+1}}\))」を満たす位置 \(p\) を並べた添字列 \(P = (p_1, \dots, p_m)\) をおきます．\(P\) の要素は口語的には「\(B\) の貪欲な添字列のなかで，同じ要素値が続くカタマリの最後にあたる添字」と説明できます．このとき，\(i = 1, \dots, m\) に対して以下が成り立ちます．

• \(A_{p_{i-1}} \neq A_{p_i}\) である(ここで，番兵 \(A_{p_0} := 0\) をおく)．
• 連続する要素 \(A_{p_{i-1} + 1},\ \cdots,\ A_{p_i}\) のうち，\(A_{p_i}\) と等しいものはちょうど \(A_{p_i}\) 個ある(ここで，番兵 \(p_0 := 0\) をおく)．

逆に，任意の \(i = 1, \dots, |P|\) で上の \(2\) 条件を満たすような添字列 \(P\) に対し，対応する \(T\) ひいては \(B\) が一意に復元できます．よって，これを満たすような空でない添字列 \(P\) の個数が答えです．

\(A_1, \dots, A_{t}\) のうち \(A_t\) に等しいものの個数を \(C_t\) とおきます．また \(J(x,c)\) を，以下を満たす値として定めます．

• \(c > 0\) の場合，\(A_{J(x,c)} = x\) かつ \(C_{J(x,c)} = c\)．
• \(c = 0\) の場合，\(J(x,c) = -1\)．

このとき，点 \(i = 1, \dots, |P|\) における上の条件は，以下のように言い換えられます．

• \(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)\) である．

上の条件は \(p_{i-1}\) の値のみに依存し，また条件を満たす \(p_{i-1}\) は連続する範囲をなします．

\(dp[p]\) を，末尾が \(p\) であるような valid な \(P\) の個数として定めます．これを \(p = 1, \dots, N\) の昇順に求めることを考えます．なお，番兵として \(dp[0] := 1\) をおきます．

このとき \(dp[p]\) の値は，\(C_{p} - A_p < 0\) の場合は \(0\) であり，そうでない場合は上で求めた範囲の \(p_{i-1}\) に対する \(dp[p_{i-1}]\) の総和として得られます．よって，\(A_{p}, C_p\) の値および一点更新・区間和取得ができればよいです．

\(A_{p}, C_p\) の値は単純な前計算によって \(O(N)\) で得られ，一点更新・区間和取得はセグメント木によってクエリあたり \(O(\log N)\) で行えます(一点更新は \(p = 1, \dots, N\) の昇順に \(1\) 回ずつであることを利用し，累積和によって全体 \(O(N)\) で行うこともできます)．

求める答えは \(dp[1], \dots, dp[N]\) の総和であり，以上を実装すれば求まります．

時間計算量は \(O(N \log N)\) (累積和で実装する場合は \(O(N)\)) となり，いずれにしても十分高速です．

実装例 (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;
}