G - Similar Adjacent Subarrays 解説 /

実行時間制限: 2 sec / メモリ制限: 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