Shil has a permutation p₁ , p₂ .. p_N of numbers from 1 to N and M queries. Each query consists of two integers l and r . Answer to each query is total number of pairs[i , j] such that l ≤ i ≤ j ≤ r and|p_i - p_j| ≤ D.

INPUT:
First line consists of three integers N, M and D. Next line consists of permutation p₁ , p₂ .. p_N of the first N natural numbers. Next M lines consists of two integers l and r .

OUTPUT:
Output M integers with i^th integer corresponding answer to i^th query.

CONSTRAINTS:
1 ≤ N, M ≤ 10⁵
1 ≤ D ≤ 10
1 ≤ p_i ≤ N
1 ≤ l ≤ r ≤ N