Problem Background

WD is deeply immersed in sequences, unable to extricate himself...

Problem Description

WD loves sequences very much. He believes that two sequences \( A \) and \( B \) are matched if and only if \( |A| = |B| \) and for \( 1 \le i, j \le |A|, A_i - B_i = A_j - B_j \). That is, they have the same length and one sequence can be transformed into the other by adding the same number to all its elements.

Now, CX has given him a large sequence of length \( n \). WD wants to know how many pairs of disjoint subsequences in the sequence are matched.

Input Format

The first line contains a number \( n \), representing the length of the sequence. The second line contains \( n \) numbers, representing the elements of the sequence.

Output Format

A single line containing a number, representing the count of matched subsequence pairs.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5

Sample Output #1

13

Sample Input #2

10
1 0 -1 -1 -2 -2 -3 -3 -4 -5

Sample Output #2

65

Notes

For the sample, any two disjoint and equally-sized subsequences are matched. There are 10 pairs for length 1 and 3 pairs for length 2, totaling 13 pairs.

$subtask1(11pts):~1\le n\le 100$

$subtask2(34pts):~1\le n\le 1,000$

$subtask3(55pts):~1\le n\le 300,000$

For all data, the absolute value of the numbers in the sequence is \( \le 10^9 \). The time limit for $subtask3$ is 3s, and for others, it is 1s.

见题面 Input 部分

见题面 Output 部分