Chika and Friendly Pairs
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 451 Accepted Submission(s): 74
Problem Description
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$.
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$.
Input
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]$。
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]$。
Output
For each task, you need to print one line, including only one integer, representing the number of "friendly pairs" in the query interval.
Sample Input
7 5 3 2 5 7 5 1 5 6 6 6 1 3 4 6 2 4 3 4
Sample Output
0 2 1 3 1