伊卡洛斯和西瓜

题目背景

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

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3 1 1 5
2 2 2
1 3

输出样例 #1

5

输入样例 #2

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

输出样例 #2

5
5
7
1

输入样例 #3

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

输出样例 #3

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$