← 返回题目列表

AtCoder · abc369_c

F. 计算算术子数组

中文机器翻译题面 查看原题

分数: 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