配点 : 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

入力例 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 が負であるような組も数えます。