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

면접 대비

시간 제한3초메모리 제한512 MB

요약

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

난이도: 보통10점 중 5점
유형: 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

길이가 $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)$ 의 개수를 한 줄에 출력한다.

예제3

예제 1
입력
```
10
3 5 3 6 3 4 10 4 5 2
```
예상 출력
```
9
```
예제 2
입력
```
3
1 2 3
```
예상 출력
```
1
```
예제 3
입력
```
3
1 2 4
```
예상 출력
```
0
```