/ 
Time Limit: 2 sec / Memory Limit: 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 数列としてあり得るものの個数を求めてください。
ただし、異なる位置から取り出した連続部分列であっても、数列として一致するものは区別せずまとめて 1 通りとして数えます。
制約
- 1 \leq N \leq 500\,000
- 1 \leq A_i \leq 9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
答えを 1 行に出力せよ。
入力例 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
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
2 6 7
出力例 2
0
A の空でない連続部分列として現れる 221 数列は存在しません。
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 of distinct 221 sequences that appear as a non-empty contiguous subsequence of A.
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 9
- 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 a single line.
Sample Input 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
Sample Output 1
14
The 221 sequences that appear as a non-empty contiguous subsequence of A are the following 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)
Sample Input 2
2 6 7
Sample Output 2
0
No 221 sequences appear as a non-empty contiguous subsequence of A.