P5161 WD and Sequences

WD spends all day immersed in sequences and cannot stop.

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.

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 one integer in a single line, the number of matching subarrays.

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