Description

WD很喜欢数列。他认为两个序列$A,B$是匹配的，当且仅当$|A|=|B|$且对于$1\le i,j\le |A|,A_i-B_i=A_j-B_j$.即长度相同且一个数列同时加上一个数可以和另一个数列完全一样。

现在CX给了他一个长度为$n$的大数列，WD希望知道，数列中有多少对不相交的子串使得他们是匹配的。

Input Format

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

Output Format

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

5
1 2 3 4 5

13

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

65

Hint

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