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