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.
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.
For each query, please print a line containing the answer.