G - 221 Subsequence 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

正整数からなる数列 X = (X_1, \dots, X_n) に対し、その連長圧縮の任意の (長さ・値) ペアにおいて長さと値が等しいとき、かつそのときに限り、X を 221 数列 と呼びます。より厳密には、以下の条件を満たす数列を 221 数列であるとします。

  • 1 \leq l \leq r \leq n を満たす整数組 (l, r) が以下の 3 つの条件をすべて満たすならば、必ず (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 で割ったあまりを求めてください。 ただし、異なる位置から取り出した部分列であっても、数列として一致するものは区別せずまとめて 1 通りとして数えます。

制約

  • 1 \leq N \leq 500\,000
  • 1 \leq A_i \leq N
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \cdots A_N

出力

答えを 1 行に出力せよ。

入力例 1

8
2 1 2 1 1 2 7 2

出力例 1

5

A の空でない部分列として現れる 221 数列は以下の 5 通りです。

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

入力例 2

5
2 3 4 5 4

出力例 2

0

A の空でない部分列として現れる 221 数列は存在しません。

入力例 3

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

出力例 3

15

Score : 600 points

Problem Statement

For a sequence X = (X_1, \dots, X_n) of positive integers, we call X a 221 sequence if and only if the length and value are equal for every (length, value) pair in its run-length encoding. More formally, a sequence satisfying the following condition is called a 221 sequence.

  • For any integer pair (l, r) satisfying 1 \leq l \leq r \leq n, if all three of the following conditions hold, then (r-l+1) = X_l.
    • l = 1 or (l \geq 2 and X_{l-1} \neq X_l)
    • r = n or (r \leq n-1 and X_{r+1} \neq X_r)
    • X_l = X_{l+1} = \dots = X_r

For example, (2,2,3,3,3,1,2,2) is a 221 sequence, but (1,1) and (4,4,1,4,4) are not 221 sequences.

You are given a sequence A = (A_1, \dots, A_N) of positive integers of length N. Find the number, modulo 998244353, of non-empty (not necessarily contiguous) subsequences of A that are 221 sequences. Even if two subsequences are extracted from different positions, they are counted as one if they are equal as sequences.

Constraints

  • 1 \leq N \leq 500\,000
  • 1 \leq A_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Output the answer on one line.

Sample Input 1

8
2 1 2 1 1 2 7 2

Sample Output 1

5

The 221 sequences that appear as non-empty subsequences of A are the following five:

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

Sample Input 2

5
2 3 4 5 4

Sample Output 2

0

No 221 sequences appear as non-empty subsequences of A.

Sample Input 3

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

Sample Output 3

15