/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ 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) の 8 通りです。
実際、(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
Score : 300 points
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