← 返回题目列表

AtCoder · abc452_g

G. 221 子串

中文机器翻译题面 查看原题

分数: 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.