Matching Substring Pairs

WD loves sequences. He considers two sequences \(A\) and \(B\) as matching if and only if \(|A|=|B|\) and for all \(1 \le i,j \le |A|\), we have \(A_i - B_i = A_j - B_j\). In other words, there exists a constant \(d\) such that \(A_i = B_i + d\) for all \(i\).

Now, given a sequence of \(n\) numbers, your task is to count the number of pairs of non-overlapping substrings that are matching. Two substrings \(S_1=[l_1, r_1]\) and \(S_2=[l_2, r_2]\) are non-overlapping if \(r_1 < l_2\) (assume \(l_1 < l_2\)).

Note: For substrings of length \(1\), the matching condition holds trivially. For substrings of length \(L \ge 2\), observe that if we define the difference sequence for a substring \(S\) as

[ \text{diff}(S) = [S_2 - S_1, S_3 - S_2, \dots, S_L - S_{L-1}], ]

then \(S_1\) and \(S_2\) are matching if and only if \(\text{diff}(S_1) = \text{diff}(S_2)\). This reformulation allows efficient grouping of substrings based on their difference patterns.

inputFormat

The first line contains an integer \(n\) (\(n \ge 1\)), the length of the sequence.

The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output a single integer: the number of pairs of non-overlapping matching substrings.

sample

4
1 2 3 4

6