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