给你一个由 $N$ 个正整数 $A=(A _ 1,A _ 2,\dots,A _ N)$ 组成的序列。

求满足 $1\leq l\leq r\leq N$ 的一对整数 $(l,r)$ 中，子序列 $(A _ l,A _ {l+1},\dots,A _ r)$ 构成算术级数的个数。

当且仅当存在一个 $d$ 使得 $x _ {i+1}-x _ i=d\\ (1\leq i < |x|)$ 是算术级数时，序列 $(x _ 1,x _ 2,\dots,x _ {|x|})$ 才是算术级数。尤其是长度为 $1$ 的序列总是算术级数。

第一行一个数字$N$

第二行N个数字$a_i$

满足条件的等差子序列个数

30%数据：$1\leq N \leq 20$

70%数据：$1\leq N \leq 1000$

100%数据：$1\leq N \leq 2\times 10^5$

- $1\leq A_i \leq 10^9$

- 所有输入值均为整数。

样例1说明：

有八对整数 $(l,r)$ 满足条件： $(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3)$ .

事实上，当 $(l,r)=(1,3)$ , $(A_l,\dots,A_r)=(3,6,9)$ 是算术级数时，它满足条件。然而，当 $(l,r)=(2,4)$ , $(A_l,\dots,A_r)=(6,9,3)$ 不是算术级数时，它不满足条件。