1524 - Artist

時間制限 3 秒 / メモリ制限 64 MB / 得点 6 / Writer ei1903 / x 1 / 統計 /


TLE
3sec
MLE
64MB
得点
6

問題

山本君は$ \ 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 \ $です。