P5161 WD与数列

WD 整日沉浸在数列中，无法自拔……

WD 很喜欢数列。他认为两个序列 $A,B$ 是匹配的，当且仅当 $|A|=|B|$ 且对于 $1\le i,j\le |A|,A_i-B_i=A_j-B_j$。即长度相同且一个数列同时加上一个数可以和另一个数列完全一样。 现在 CX 给了他一个长度为 $n$ 的大数列，WD 希望知道，数列中有多少对不相交的子串使得他们是匹配的。

第一行一个数 $n$，表示数列长度。第二行 $n$ 个数，表示序列中的数字。

共一行一个数，为匹配的子串个数。

对于样例，任意两个不相交且长度相等的子串都是匹配的，长度为 1 时有 10 种，长度为 2 时有 3 种，因此总共有 13 种。 $\text{subtask1}(11pts):~1\le n\le 100$ $\text{subtask2}(34pts):~1\le n\le 1,000$ $\text{subtask3}(55pts):~1\le n\le 300,000$ 对于所有数据，数列中数字的**绝对值** $\le 10^9$。$subtask3$ 的时限为 3s，其它为 1s。