AT_abc446_g [ABC446G] 221 Subsequence

对于一个由正整数组成的序列 $X = (X_1, \dots, X_n)$，我们称 $X$ 是一个 **221 序列**，当且仅当对其行程长度编码中的每一对（长度，数值），长度和数值都相等。更正式地说，满足以下条件的序列被称为 221 序列： - 对于任意整数对 $(l, r)$，其中 $1 \leq l \leq r \leq n$，如果以下三个条件都成立，则有 $(r-l+1) = X_l$。 - $l = 1$ 或（$l \geq 2$ 且 $X_{l-1} \neq X_l$） - $r = n$ 或（$r \leq n-1$ 且 $X_{r+1} \neq X_r$） - $X_l = X_{l+1} = \dots = X_r$ 例如，$(2,2,3,3,3,1,2,2)$ 是一个 221 序列，但 $(1,1)$ 和 $(4,4,1,4,4)$ 不是 221 序列。 给定一个长度为 $N$ 的正整数序列 $A = (A_1, \dots, A_N)$，求 $A$ 的所有非空（不一定连续）子序列中，不同的 221 序列的数量，结果对 $998244353$ 取模。即使两个子序列来源于不同位置，只要它们作为序列完全相同，也只计数一次。

输入按以下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出一行，为答案。

### 样例解释 1 作为 $A$ 的非空子序列出现的 221 序列有以下五个： - $(1)$ - $(1,2,2)$ - $(2,2)$ - $(2,2,1)$ - $(2,2,1,2,2)$ ### 样例解释 2 没有 221 序列作为 $A$ 的非空子序列出现。 ### 约束条件 - $1 \leq N \leq 500\,000$ - $1 \leq A_i \leq N$ - 所有输入都是整数。 由 ChatGPT 5 翻译