問題
山本君は$ \ N \ $個の塗料を持っており、$i \ $番目の塗料の色は整数$ \ C_i \ $で表されます。
山本君はこれらの塗料を使って$ \ M \ $枚の絵画を作成しようとしており、$i \ $番目の絵画では$ \ N \ $個の塗料のうち$ \ l_i \ $番目から$ \ r_i \ $番目までを使用します。
ここで、絵画の美しさを「使用する塗料の中から$ \ 2 \ $つの塗料を選んだ時、選んだ塗料の色の差の絶対値が$ \ D \ $以下となるような選び方の総数」とします。
$M \ $個の絵画について美しさを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N \ M \ D$ $C_1 \ C_2 \ \ldots \ C_N$ $l_1 \ r_1$ $l_2 \ r_2$ $\vdots$ $l_M \ r_M$
出力
各絵画の美しさを改行区切りで出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,M \leq 10^5$
- $0 \leq D \leq 10^9$
- $1 \leq C_i \leq 10^9$
- $1 \leq l_i \leq r_i \leq N$
入出力例
入力例
5 4 2 1 3 2 2 5 1 3 2 5 4 5 5 5
出力例
3 4 0 0
- 絵画1:$(C_1,C_2),(C_1,C_3),(C_2,C_3) \ $の$ \ 3 \ $通りなので美しさは$ \ 3 \ $です。
- 絵画2:$(C_2,C_3),(C_2,C_4),(C_2,C_5),(C_3,C_4) \ $の$ \ 4 \ $通りなので美しさは$ \ 4 \ $です。
- 絵画3:差が$ \ 2 \ $以下となるような選び方は存在しないため美しさは$ \ 0 \ $です。
- 絵画4:一つの塗料しか使わないため美しさは$ \ 0 \ $です。