题目描述

一个区间中如果存在这样的一对数字 $<A,B>$ 并且 $abs(A-B)$ 不大于 $K$ ，我们就称这一对数字为奇妙的数字对。

现在给出你长为n的序列，求奇妙数字对 $<i，j>$ 在 $[L,R]$ 中的个数。

输入格式

第一行输入三个数字 $N,M,K$;

第二行有 $N$ 个数字，代表序列。

第三行有 $M$ 次询问 $[L,R]$ 。

输出格式

输出 $M$ 行。

每行一个数字，代表询问区间的奇妙数字对的个数。

样例

样例输入

7 5 3   
2 5 7 5 1 5 6   
6 6   
1 3   
4 6   
2 4   
3 4   

样例输出

0
2
1
3
1  

数据范围与提示

对于 $100\%$ 的数据，$ 1 \leq n \leq 27000, 1 \leq m \leq 27000， 1 \leq k \leq 10 ^ 9$ ， $n$ 个数字都不超过 $10^9$ 。