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

5
1 2 3 4 5

输出样例 #1

13

输入样例 #2

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

输出样例 #2

65

说明

对于样例,任意两个不相交且长度相等的子串都是匹配的,长度为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.