题目描述

给定参数 $c,d$ 和一个长度为 $n$ 的序列 $\{a\}$。有 $q$ 个区间，对于每个区间 $[l,r]$，求出 $\sum\limits_{x=l}^{r} \sum\limits_{y=x}^r [c\le (\sum\limits_{i=x}^{y} \sum\limits_{j=i+1}^{y} [a_i>a_j])\le d]$。

注意区别以上两种中括号：

1. $[l,r]$ 代表一个区间。
2. $[p]$ 为艾弗森括号，其中 $p$ 是一个仅有真假两种取值的表达式。若 $p$ 为真，则 $[p]=1$，否则 $[p]=0$。

通俗的讲，对于每个区间 $[l,r]$，求出区间内有多少非空子区间的逆序对个数在 $c$ 到 $d$ 之间（含 $c$ 和 $d$）。

输入格式

第一行包含三个正整数 $n,c,d$。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示序列第 $i$ 项 $a_i$。

第三行一个整数 $q$，表示区间个数。

接下来的 $q$ 行，第 $i$ 行包含两个正整数 $l_i,r_i$，表示第 $i$ 个区间。

输出格式

输出 $q$ 行，第 $i$ 行表示对于第 $i$ 个区间，这个区间内有多少非空子区间的逆序对个数在 $c$ 到 $d$ 之间（含 $c$ 和 $d$）。

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

6
2
2

10 2 4
1 9 2 5 7 3 6 10 4 8
10
1 3
2 4
3 5
4 9
1 10
2 9
5 7
6 9
2 6
7 7

0
1
0
7
17
12
1
2
4
0

25 3 39
20 19 18 17 16 15 18 14 13 12 11 19 17 10 9 8 7 9 6 8 5 4 6 7 3
20
17 18
1 10
20 25
4 9
13 15
6 21
3 7
12 17
18 21
3 12
5 17
3 4
8 18
17 22
19 21
2 23
14 22
13 20
18 25
11 20

0
33
6
8
1
76
5
10
1
33
55
0
40
7
0
123
24
18
15
32

25 40 1000
20 19 18 17 16 15 18 14 13 12 11 19 17 10 9 8 7 9 6 8 5 4 6 7 3
20
17 18
1 10
20 25
4 9
13 15
6 21
3 7
12 17
18 21
3 12
5 17
3 4
8 18
17 22
19 21
2 23
14 22
13 20
18 25
11 20

0
1
0
0
0
21
0
0
0
0
6
0
1
0
0
77
0
0
0
0

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

0
0
0

提示

本题采用捆绑测试。

对于所有数据，$1\le n,q,a_i\le 5\times 10^5$，$1\le c,d\le 10^{12}$，对于每个 $1\le i\le q$，满足 $1\le l_i\le r_i\le n$。