CPAIR2 - Counting diff-pairs

no tags 

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
aimbot: 2018-01-12 23:33:20

awesome problem, I love it

basilisk1995: 2017-11-04 03:16:54

Limits of K should be mentioned. Until then it is safe to assume K can be any positive integer.

darryl: 2016-08-05 11:47:16

cool prob.
learn something new.

Zhouxing Shi: 2012-10-05 12:00:16

nice problem~~

Damian Straszak: 2012-07-04 18:52:37

Very nice problem.


Added by:Buda IM
Date:2012-06-03
Time limit:1s-2.756s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem