分数: 600 点
问题陈述
对于序列 X = (X_1, \dots, X_n) 的正整数,我们称之为 X a 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 序列。
给你一个序列 A = (A_1, \dots, A_N) 长度为正整数 N。查找显示为非空的不同 221 序列的数量 连续子序列 of A.
即使从不同位置提取两个子序列,如果它们作为序列相等,则将它们算作一个。
约束
- 1 \leq N \leq 500\,000
- 1 \leq A_i \leq 9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
在一行上输出答案。
示例输入 1
23 2 2 3 3 3 1 1 1 3 3 3 1 2 2 2 1 9 1 4 4 4 4 4
示例输出 1
14
作为非空连续子序列出现的 221 个序列 A 如下 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
2 6 7
示例输出 2
0
没有 221 个序列作为非空连续子序列出现 A.