Background

WD spends all day immersed in sequences and cannot stop.

Problem Description

WD really likes sequences. He thinks two sequences $A, B$ match 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 by adding the same number to every element of one sequence, it can become exactly the other sequence.

Now CX gives him a large sequence of length $n$. WD wants to know how many pairs of non-overlapping subarrays in the sequence are matching.

Input Format

The first line contains an integer $n$, representing the length of the sequence. The second line contains $n$ integers, representing the numbers in the sequence.

Output Format

Output one integer in a single line, the number of matching subarrays.

5
1 2 3 4 5

13

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

65

Hint

For the sample, any two non-overlapping subarrays with the same length are matching. For length $1$ there are $10$ pairs, and for length $2$ there are $3$ pairs, so there are $13$ pairs in total.

$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 each number in the sequence is $\le 10^9$. The time limit for $subtask3$ is $3\text{s}$, and for the others it is $1\text{s}$.

Translated by ChatGPT 5