← 返回题目列表

AtCoder · abc446_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。求模数 998244353,非空(不一定连续)子序列 A 是 221 个序列。 即使从不同位置提取两个子序列,如果它们作为序列相等,也算为一个。

约束

  • 1 \leq N \leq 500\,000
  • 1 \leq A_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

在一行上输出答案。


示例输入 1

8
2 1 2 1 1 2 7 2

示例输出 1

5

作为非空子序列出现的 221 个序列 A 有以下五项:

  • (1)
  • (1,2,2)
  • (2,2)
  • (2,2,1)
  • (2,2,1,2,2)

示例输入 2

5
2 3 4 5 4

示例输出 2

0

没有 221 个序列作为非空子序列出现 A.


示例输入 3

20
2 2 3 1 1 4 1 4 1 4 2 4 1 2 1 4 4 1 1 4

示例输出 3

15