问题描述

给定一个 $N$ 个正整数的序列 $A=(A_1,A_2,\dots,A_N)$。

找出满足 $1≤l≤R≤N$ 的整数对 $(l,r)$ 的数目，使得子序列 $(A_l,A_{l+1},\dots,A_r)$ 形成等差数列。

一个数列 $(x_1,x_2,\dots,x_{|x|})$ 是一个等差数列当且仅当存在一个 $d$ 使得 $x_{i+1}-x_i=d(1≤i<|x|)$。特别地，长度为 $1$ 的序列总是等差数列。

数据规模

$1≤N≤2×10^5$

$1≤A_i≤10^9$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N$

$A_1\ A_2\ \dots\ A_N$

输出

打印答案。

4
3 6 9 3

8

有八对整数 $(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)$ 不是等差数列，因此不满足条件。

5
1 1 1 1 1

15

所有整数对 $(l,r)(1≤l≤R≤5)$ 满足条件。

8
87 42 64 86 72 58 44 30

22