背景

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$ 个数，表示序列中的数字。

输出格式

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

5
1 2 3 4 5

13

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

65

提示

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