Problem Description

DZY has a array $a$, consisting of $n$ positive integers, indexed from 1 to $n$.

Let's denote the number with index $i$ as $a_i$.

DZY wants to count, with a given pair ($l,r$)$(l\leq r)$, how many pairs of integers $i$ and $j$ are there, such that $l \leq i \leq j \leq r$ and the sequence $b=a_{i}a_{i+1}\cdots a_{j}$ has exactly $k$ inversions.

Moreover, DZY has $q$ queries.

Input

The input consists several test cases.($TestCase\leq 5$)

The first line contains three integers $n, q, k(1 \leq n \leq 10^5, 1 \leq q \leq 10^5, 0 \leq k \leq 10^{18})$.

The next line contains $n$ positive integers, separated by single spaces, $a_1,a_2,\cdots ,a_n(1 \leq a_i \leq 10^9)$.

Each of the next $q$ lines has two integers: $l,r$, representing a query.

Output

For each query, please print a line containing the answer.

6 4 1
3 1 5 4 2 6
2 4
2 3
3 4
1 5

2
0
1
5

Hint

query 1. (2,4), (3,4) are ok.
query 2. No such pair.
query 3. (3,4) is ok.
query 4. (1,2), (1,3), (2,4), (3,4), (4,5) are ok.