分数: 300 点
问题陈述
给你一个序列 N 正整数 A=(A_1,A_2,\dots,A_N).
查找整数对的数量 (l,r) 满意 1\leq l\leq r\leq N 这样子序列 (A_l,A_{l+1},\dots,A_r) 形成算术级数。
一个序列 (x_1,x_2,\dots,x_{|x|}) 是算术级数当且仅当存在 d 这样 x_{i+1}-x_i=d\ (1\leq i < |x|)。 特别地,长度的序列 1 始终是算术级数。
约束
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
4 3 6 9 3
示例输出 1
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) 不是等差数列,因此不满足条件。
示例输入 2
5 1 1 1 1 1
示例输出 2
15
所有整数对 (l,r)\ (1\leq l\leq r\leq 5) 满足条件。
示例输入 3
8 87 42 64 86 72 58 44 30
示例输出 3
22