103692: [Atcoder]ABC369 C - Count Arithmetic Subarrays

Problem Statement

You are given a sequence of $N$ positive integers $A=(A_1,A_2,\dots,A_N)$.

Find the number of pairs of integers $(l,r)$ satisfying $1\leq l\leq r\leq N$ such that the subsequence $(A_l,A_{l+1},\dots,A_r)$ forms an arithmetic progression.

A sequence $(x_1,x_2,\dots,x_{|x|})$ is an arithmetic progression if and only if there exists a $d$ such that $x_{i+1}-x_i=d\ (1\leq i < |x|)$. In particular, a sequence of length $1$ is always an arithmetic progression.

Constraints

• $1\leq N \leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers $(l,r)$ satisfying the condition: $(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3)$.

Indeed, when $(l,r)=(1,3)$, $(A_l,\dots,A_r)=(3,6,9)$ is an arithmetic progression, so it satisfies the condition. However, when $(l,r)=(2,4)$, $(A_l,\dots,A_r)=(6,9,3)$ is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers $(l,r)\ (1\leq l\leq r\leq 5)$ satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

问题陈述

给你一个由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$)构成一个等差数列。

一个序列($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