/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下の条件をすべて満たすような 3 整数の組 (a,b,c) の総数を求めてください。
- 0 \leq a \lt b \lt c \leq N
- b-a=c-b
- A_{a+i} \neq A_{b+i} を満たす 1 以上 b-a 以下の整数 i がちょうど 1 つ存在する
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを 1 行で出力せよ。
入力例 1
7 1 2 1 3 1 2 1
出力例 1
10
条件を満たす (a,b,c) は (0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7) の 10 個です。
入力例 2
2 1000000000 1000000000
出力例 2
0
入力例 3
6 1 2 3 1 2 4
出力例 3
6
Score : 625 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (a,b,c) that satisfy all of the following conditions.
- 0 \leq a \lt b \lt c \leq N
- b-a=c-b
- There is exactly one integer i between 1 and b-a, inclusive, such that A_{a+i} \neq A_{b+i}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer in one line.
Sample Input 1
7 1 2 1 3 1 2 1
Sample Output 1
10
The triples (a,b,c) that satisfy the conditions are the following ten: (0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7).
Sample Input 2
2 1000000000 1000000000
Sample Output 2
0
Sample Input 3
6 1 2 3 1 2 4
Sample Output 3
6