問題文

長さ $N$ の整数列 $A = ( A_1, A_2, \dots, A_N )$ と正整数 $D$ が与えられます。$A$ の部分列であって、長さが $3$、公差が $D$ の等差数列となるものはいくつあるか求めてください。

より厳密には、次の条件を満たす $(i, j, k)$ の組の個数を求めてください。

• $1 \le i < j < k \le N$
• $A_i < A_j < A_k$
• $A_j - A_i = A_k - A_j = D$

制約

• $3 \le N \le 10^5$
• $1 \le D \le 5 \times 10^8$
• $0 \le A_i \le 10^9$ $(1 \le i \le N)$
• 入力はすべて整数

入力

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

出力

条件を満たす $(i, j, k)$ の組の個数を $1$ 行で出力してください。

サンプル

7 2
0 2 5 1 4 3 6

2

6 1
1 1 2 2 3 3

8