G - Fine Triplets Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

整数 A,B,C ( A<B<C ) が B-A = C-B を満たす時、 (A,B,C) を 良い三つ組 と呼びます。
N 要素からなる正整数の集合 S=\{ S_1,S_2,\dots,S_N \} が与えられるので、 A,B,C \in S なる良い三つ組の個数を求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 10^6
  • 1 \le S_i \le 10^6
  • S の要素は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 S_2 \dots S_N

出力

答えを整数として出力せよ。

入力例 1

5
8 3 1 5 2

出力例 1

3

S=\{8,3,1,5,2\} です。数えるべき良い三つ組は以下の 3 つです。

  • (1,2,3)
  • (1,3,5)
  • (2,5,8)

入力例 2

7
300000 100000 499998 499999 200000 400000 500000

出力例 2

5

入力例 3

10
13 1 16 15 12 4 7 10 2 19

出力例 3

10

Score : 600 points

Problem Statement

For integers A, B, C ( A < B < C ), if they satisfy B-A = C-B, then (A, B, C) is called a fine triplet.
You are given a set of N distinct positive integers S = \{ S_1, S_2, \dots, S_N \}. Find the number of fine triplets (A, B, C) with A, B, C \in S.

Constraints

  • All input values are integers.
  • 1 \le N \le 10^6
  • 1 \le S_i \le 10^6
  • The elements of S are distinct.

Input

The input is given from Standard Input in the following format:

N
S_1 S_2 \dots S_N

Output

Print the number of fine triplets as an integer.

Sample Input 1

5
8 3 1 5 2

Sample Output 1

3

Here, S = \{8,3,1,5,2\}. The fine triplets to be counted are the following three:

  • (1,2,3)
  • (1,3,5)
  • (2,5,8)

Sample Input 2

7
300000 100000 499998 499999 200000 400000 500000

Sample Output 2

5

Sample Input 3

10
13 1 16 15 12 4 7 10 2 19

Sample Output 3

10