U101170 伊卡洛斯和西瓜

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

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

无

无

[**【大样例】**](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$