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