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 翻译