/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
整数の 2 つ組 (i,j)\ (1\le i\lt j\le N) のうち、j-i=A _ i+A _ j を満たすものがいくつあるか求めてください。
制約
- 1\le N\le2\times10 ^ 5
- 1\le A _ i\le2\times10 ^ 5\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N
出力
答えを出力せよ。
入力例 1
9 3 1 4 1 5 9 2 6 5
出力例 1
3
例えば、(i,j)=(4,7) とすると、j-i=7-4=3 かつ A _ i+A _ j=1+2=3 が成り立つので、j-i=A _ i+A _ j です。
一方で、(i,j)=(3,8) とすると、j-i=8-3=5 かつ A _ i+A _ j=4+6=10 となるので、j-i\ne A _ i+A _ j です。
(i,j)=(1,9),(2,4),(4,7) の 3 組だけが条件を満たすので、3 を出力してください。
入力例 2
3 123456 123456 123456
出力例 2
0
条件を満たす組が存在しない場合もあります。
入力例 3
30 8 3 6 4 9 6 5 6 5 6 3 4 7 3 7 4 9 8 5 8 3 6 8 8 4 5 5 5 6 5
出力例 3
17
Score : 300 points
Problem Statement
You are given an integer sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.
Find how many pairs of integers (i,j)\ (1\le i\lt j\le N) satisfy j-i=A _ i+A _ j.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le A _ i\le2\times10 ^ 5\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N
Output
Output the answer.
Sample Input 1
9 3 1 4 1 5 9 2 6 5
Sample Output 1
3
For example, when (i,j)=(4,7), we have j-i=7-4=3 and A _ i+A _ j=1+2=3, so j-i=A _ i+A _ j.
In contrast, when (i,j)=(3,8), we have j-i=8-3=5 and A _ i+A _ j=4+6=10, so j-i\ne A _ i+A _ j.
Only the three pairs (i,j)=(1,9),(2,4),(4,7) satisfy the condition, so output 3.
Sample Input 2
3 123456 123456 123456
Sample Output 2
0
There may be no pairs that satisfy the condition.
Sample Input 3
30 8 3 6 4 9 6 5 6 5 6 3 4 7 3 7 4 9 8 5 8 3 6 8 8 4 5 5 5 6 5
Sample Output 3
17