/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 以上 \textbf{10} 以下の整数からなる長さ N の数列 A が与えられます．
1\leq l \leq r\leq N を満たす整数組 (l,r) であって，以下の条件を満たすものを良い組と呼びます．
- 数列 (A_l,A_{l+1},\ldots,A_r) は長さ 3 の等差数列を（連続とは限らない）部分列として含む．より厳密には，l \leq i < j < k\leq r を満たす整数組 (i,j,k) であって， A_j - A_i = A_k - A_j なるものが存在する．
良い組の個数を求めてください．
制約
- 3 \leq N \leq 10^5
- 1\leq A_i \leq 10
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N A_1 \ldots A_N
出力
答えを出力せよ．
入力例 1
5 5 3 4 1 5
出力例 1
3
良い組は (l,r)=(1,4),(1,5),(2,5) の 3 つです．
例えば，数列 (A_1,A_2,A_3,A_4) は (5,3,1) という長さ 3 の等差数列を部分列として含むので (1,4) は良い組です．
入力例 2
3 1 2 1
出力例 2
0
良い組が存在しない場合もあります．
入力例 3
9 10 10 1 3 3 7 2 2 5
出力例 3
3
Score: 500 points
Problem Statement
You are given a sequence A of length N consisting of integers between 1 and \textbf{10}, inclusive.
A pair of integers (l,r) satisfying 1\leq l \leq r\leq N is called a good pair if it satisfies the following condition:
- The sequence (A_l,A_{l+1},\ldots,A_r) contains a (possibly non-contiguous) arithmetic subsequence of length 3. More precisely, there is a triple of integers (i,j,k) with l \leq i < j < k\leq r such that A_j - A_i = A_k - A_j.
Find the number of good pairs.
Constraints
- 3 \leq N \leq 10^5
- 1\leq A_i \leq 10
- All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
5 5 3 4 1 5
Sample Output 1
3
There are three good pairs: (l,r)=(1,4),(1,5),(2,5).
For example, the sequence (A_1,A_2,A_3,A_4) contains an arithmetic subsequence of length 3, which is (5,3,1), so (1,4) is a good pair.
Sample Input 2
3 1 2 1
Sample Output 2
0
There may be cases where no good pairs exist.
Sample Input 3
9 10 10 1 3 3 7 2 2 5
Sample Output 3
3