DZY Loves Inversions

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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.

Sample Input

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

Sample Output

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.

Hint

hujie

Source

BestCoder Round #35

提交代码