등차수열을 이루는 세 항의 개수

i < j < k이고 A_i, A_j, A_k가 등차수열을 이루는 인덱스 삼중항의 개수를 센다.

보통5해시맵수학면접 대비아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제3

문제

길이가 $N$ 인 수열 $A_1, A_2, \dots, A_N$ 이 주어진다. 세 인덱스 $i < j < k$ 가 $A_j - A_i = A_k - A_j$ 를 만족하면 세 항 $A_i, A_j, A_k$ 는 등차수열을 이룬다. 이 조건은 $A_i + A_k = 2 A_j$ 와 같다.

조건을 만족하는 $(i, j, k)$ 의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 $N$ 이 주어진다. ( $3 \le N \le 100000$ )

둘째 줄에 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. ( $1 \le A_i \le 30000$ )

출력

$i < j < k$ 이면서 $A_j - A_i = A_k - A_j$ 를 만족하는 $(i, j, k)$ 의 개수를 한 줄에 출력한다.