D - Nice Couples
解説
/
実行時間制限: 5 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
長さ N の整数列 A_1, \ldots, A_N が与えられます。 次の条件を満たす整数の組 \left(i,j \right) \left(1 \le i < j \le N \right) の数を出力してください。
- A_i - A_j は j - i で割り切れる。
制約
- 2 \le N \le 10^5
- 0 \le A_i \le 10^5
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
答えを出力せよ。
入力例 1
4 0 2 3 9
出力例 1
4
(1, 2), (1, 4), (2, 3), (3, 4) の 4 個です。
入力例 2
10 1 2 3 1 2 3 1 2 3 4
出力例 2
23
a_i - a_j が負であるような組も数えます。