给你一个由 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) 不是算术级数时，它不满足条件。