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希望知道，数列中有多少对不相交的子串使得他们是匹配的。

无

无

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