등차 부분수열

시간 제한1초메모리 제한128 MB

요약

1부터 n까지의 순열에서 값이 길이가 3인 등차수열을 이루는 인덱스 삼중항 i<j<k의 개수를 셉니다.

난이도: 보통10점 중 7점
유형: 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

어떤 $n$ 에 대해 $1, 2, \ldots, n$ 을 원소로 하는 순열이 주어진다. 순열의 원소를 나오는 순서대로 $a_1, a_2, \ldots, a_n$ 이라고 하자. 길이가 정확히 $3$ 인 등차 부분수열이 몇 개인지 세는 것이 목표다. 더 정확히 말하면, $i < j < k$ 이면서 $a_j - a_i = a_k - a_j$ 를 만족하는 삼중쌍 $(i, j, k)$ 의 개수를 구하라.

입력

첫째 줄에 정수 $n$ $(1 \le n \le 200\,000)$ 이 주어진다. 둘째 줄에는 순열을 나타내는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다.

출력

주어진 순열에서 길이가 $3$ 인 등차 부분수열의 개수를 출력한다. 답은 $1\,000\,000$ 을 넘지 않는다고 가정해도 된다.

예제7

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