Arithmetic Subsequences

Time limit1sMemory limit128 MB

Summary

Count index triples i<j<k in a permutation of 1 to n whose values form a three-term arithmetic progression.

Level: Medium7 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

You are given a permutation of the numbers $1, 2, \ldots, n$ for some $n$ . Let the elements of the permutation, in order, form a sequence $a_1, a_2, \ldots, a_n$ . Your task is to count how many arithmetic subsequences of $a$ have length exactly $3$ . More precisely, count the triples $(i, j, k)$ such that $i < j < k$ and $a_j - a_i = a_k - a_j$ .

Input

The first line contains one integer $n$ $(1 \le n \le 200\,000)$ . The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ describing the permutation.

Output

Print the number of length- $3$ arithmetic subsequences of the given permutation. You may assume the answer does not exceed $1\,000\,000$ .

Examples7

Example 1
Input
```
5
1 5 4 2 3
```
Expected output
```
2
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
2
2 1
```
Expected output
```
0
```
Example 4
Input
```
3
1 2 3
```
Expected output
```
1
```
Example 5
Input
```
3
3 2 1
```
Expected output
```
1
```
Example 6
Input
```
3
2 1 3
```
Expected output
```
0
```
Example 7
Input
```
6
1 2 3 4 5 6
```
Expected output
```
6
```