AT_abc452_g [ABC452G] 221 Substring

对于一个正整数序列 $X = (X_1, \dots, X_n)$，当且仅当它的游程编码中的每一个（长度，数值）对，其长度等于数值时，称 $X$ 为 **221 序列**。更正式地，满足下述条件的序列称为 221 序列： - 对于任意满足 $1 \leq l \leq r \leq n$ 的整数对 $(l, r)$，如果同时满足以下三个条件，则有 $(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 序列个数。 即使两个子序列取自不同的位置，只要它们完全相同，则只计为一次。

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

输出一行，表示答案。

### 样例解释 1 出现在 $A$ 的非空连续子序列中的 221 序列共有如下 $14$ 个： - $(1)$ - $(1,2,2)$ - $(1,3,3,3)$ - $(1,3,3,3,1)$ - $(1,3,3,3,1,2,2)$ - $(1,4,4,4,4)$ - $(2,2)$ - $(2,2,1)$ - $(2,2,3,3,3)$ - $(2,2,3,3,3,1)$ - $(3,3,3)$ - $(3,3,3,1)$ - $(3,3,3,1,2,2)$ - $(4,4,4,4)$ ### 样例解释 2 不存在出现在 $A$ 的非空连续子序列的 221 序列。 ### 数据范围 - $1 \leq N \leq 500\,000$ - $1 \leq A_i \leq 9$ - 所有输入均为整数。 由 ChatGPT 5 翻译