题目描述

你的朋友 ezoilearner​ 没有找到女朋友，于是他给了你一个长度为 $n$ 的数列 $s$。

你需要找出有多少个三元组 $(a,b,len)$，满足

• $1 \leq a \leq a+len-1 < b \leq b+len-1 \leq n$
• $\forall i \in [0,len-1] \ s_{a+i}-s_{a} = s_{b+i} - s_{b}$

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数表示 $s$。

输出格式

一行一个整数表示答案。

样例

样例输入 1

5
1 2 1 3 4

样例输出 1

11

样例输入 2

10
1 7 8 2 3 9 6 0 6 1

样例输出 2

50

样例解释 2

所有 $len=1,a < b$ 的三元组都满足条件，共有 45 个。

满足条件的三元组还有 $(1,5,2),(1,8,2),(2,4,2),(3,7,2),(5,8,2)$。

更多样例请见下发文件。

数据范围和提示