伊卡洛斯和西瓜

> 我是娱乐用（战略型）人造天使，α型号「伊卡洛斯」，将满足您的所有愿望，My Master。——伊卡洛斯 > 定是为了与你相遇，我才从天而降。——伊卡洛斯  伊卡洛斯因喜欢被智树摸头的感觉，对圆圆的东西充满着浓厚的兴趣（比如西瓜）。 智树为了让她开心，在后院里种了一行魔法西瓜，每天 $0:00$ 时，会瞬间长出来并达到最大重量。

伊卡洛斯每天至少要吃 $X$ $kg$ 西瓜才会满足，但由于身体承受能力有限，最多不能超过 $Y$ $kg$。 智树并不想让她一次性把所有西瓜都吃光，所以每天会**开放某一块连续的区域（包含边界）**，伊卡洛斯可以在其中**任选一个起点从左到右依次吃掉若干个西瓜**。 现在妮姆芙从智树那里得知了每个西瓜的最大重量，她想知道伊卡洛斯**每天有多少种吃西瓜的方案**。 您作为一个可以轻松 AK IOI 的巨佬，能帮帮可爱的妮姆芙吗？

第一行三个整数 $n,T,X,Y$，其中 $n$ 表示魔法西瓜的个数，$T$ 表示天数，$X,Y$ 含义如上。 接下来一行 $n$ 个整数，其中第 $i$ 个数表示第 $i$ 个西瓜的最大重量 $a_i$ 。 然后有 $T$ 行，每行两个整数 $L,R$，表示每天智树开放区域的左右边界。

输出每天伊卡洛斯可以选择的方案数。

3 1 1 5
2 2 2
1 3

5

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

5
5
7
1

10 5 1 1000
153 487 10 145 45 363 14 4 1 475
1 5
1 10
3 5
4 8
2 9

15
43
6
15
32

[**【大样例】**](https://files.cnblogs.com/files/Xing-Ling/Ikaros_Bigdata.rar) **【样例解释】** 对于样例一：第 $1,2,3$ 个西瓜最大重量均为 $2$，伊卡洛斯第一天可以选择依次吃掉 $\{1\},\{2\},\{3\},\{1,2\},\{2,3\}$，共 $5$ 种方案。 **【数据范围】** $Subtask\ 1$ $(10 pt)$ $:$ $1 \leqslant n \leqslant 200,$ $1 \leqslant T \leqslant 2000$ $Subtask\ 2$ $(50 pt)$ $:$ $1 \leqslant n \leqslant 5*10^4,$ $1 \leqslant T \leqslant 5*10^4$ $Subtask\ 3$ $(40 pt)$ $:$ $1 \leqslant n \leqslant 10^6,$ $1 \leqslant T \leqslant 10^6$ $100 \%:$ $1 \leqslant X \leqslant Y \leqslant n*10^9,$ $1 \leqslant a_i \leqslant 10^9,$ $1 \leqslant L \leqslant R \leqslant n$