CPAIR2  Counting diffpairs
You are given sequence A of N integers. You are also given integer K and M queries. Each query consists of two integers l, r. For each query output number of pairs i, j such that l <= i < j <= r and abs(A[i]  A[j]) >= K.
Indexing starts with 1.
N <= 50000
M <= 50000
1 <= A[i] <= 100000
NOTE: All tests are randomly generated.
Input
First line of input contains integers N, M, K in this order.
Second line contains N integers representing array A.
Next M lines describe queries.
Output
Output answer for each query.
Example
Input: 3 1 2
1 2 3
1 3
Output: 1
hide comments
darryl:
20160805 11:47:16
cool prob.


Zhouxing Shi:
20121005 12:00:16
nice problem~~ 

Damian Straszak:
20120704 18:52:37
Very nice problem. 
Added by:  Buda IM 
Date:  20120603 
Time limit:  0.183s2.756s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 