5196：DZY Loves Inversions

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.