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
DK...:
20190301 00:56:34
n*sqrt(n)*log(n) works fine!, and it's not necessary to use printf/scanf methods 

shuvam_kedia:
20180921 16:26:28
Time limit is strict .Use BIT instead of segment tree. 

aimbot:
20180112 23:33:20
awesome problem, I love it 

basilisk1995:
20171104 03:16:54
Limits of K should be mentioned. Until then it is safe to assume K can be any positive integer. 

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:  1s2.756s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 