统计等差子数组

题目描述

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

求满足 $1\le l\le r\le 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\le i \lt |x|)$。 特别地，长度为 $1$ 的序列总是等差数列。

输入格式

输入按以下格式从标准输入给出：

$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

所有满足 $1\le l\le r\le 5$ 的整数对 $(l,r)$ 都满足条件。

8
87 42 64 86 72 58 44 30

22

数据范围

• $1\le N \le 2\times 10^5$
• $1\le A_i \le 10^9$
• 所有输入值均为整数。