问题描述
DZY有一个序列$a$，一共由$n$个正整数组成，下标为$1$到$n$。我们定义第$i$个数为$a_i$。
DZY每次给定一个数对($l,r$)$(l\leq r)$，他想计算有多少个数对($i,j$)，满足$l \leq i \leq j \leq r$，且序列 $b=a_{i}a_{i+1}\cdots a_{j}$ 有恰好$k$个逆序对。而且，DZY会询问你$q$次噢。
输入描述
输入有多组测试数据。($TestCase\leq 5$)
第一行三个整数$n, q, k(1 \leq n \leq 10^5, 1 \leq q \leq 10^5, 0 \leq k \leq 10^{18})$.
第二行有 $n$ 个正整数，表示 $a_1,a_2,\cdots ,a_n(1 \leq a_i \leq 10^9)$.
接下来$q$行，每行两个正整数$l,r$, 表示一组询问。
输出描述
对于每个询问，输出一行一个数表示答案。
输入样例
6 4 1
3 1 5 4 2 6
2 4
2 3
3 4
1 5
输出样例
2
0
1
5
Hint
询问 1. (2,4), (3,4) are ok.
询问 2. No such pair.
询问 3. (3,4) is ok.
询问 4. (1,2), (1,3), (2,4), (3,4), (4,5) are ok.
