Chika and Friendly Pairs

Chika gives you an integer sequence $a_1, a_2, \ldots, a_n$ and $m$ tasks. For each task, you need to answer the number of "friendly pairs" in a given interval.

friendly pair: for two integers $a_i$ and $a_j$, if $i<j$ and the absolute value of $a_i-a_j$ is no more than a given constant integer $K$, then $(i, j)$ is called a "friendly pair".A friendly pair $(i, j)$ in a interval $[L,R]$ should satisfy $L \leq i < j \leq R$.

The first line contains $3$ integers $n$ $(1 \leq n \leq 27000)$, $m$ $(1 \leq m \leq 27000)$ and $K$ $(1 \leq K \leq 10^9)$, representing the number of integers in the sequence $a$, the number of tasks and the given constant integer.
The second line contains $n$ non-negative integers, representing the integers in the sequence $a$. Every integer of sequence $a$ is no more than $10^9$.
Then $m$ lines follow, each of which contains two integers $L$, $R$ $(1 \leq L \leq R \leq n)$. The meaning is to ask the number of "friendly pairs" in the interval $[L,R]$。

For each task, you need to print one line, including only one integer, representing the number of "friendly pairs" in the query interval.

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

2019CCPC湖南全国邀请赛（广东省赛、江苏省赛）重现赛