题目描述

在那座以精密著称的未来之城中，能源并不是以恒定的形式存在。它更像是一种会随时间起伏的“余量”：有时略有盈余，有时略显亏空。系统会为每一天留下一个对应的记录，用以描述这种微小的变化。

然而，工程师们真正关心的，从来不是孤立的一天。他们更关注一段连续时间里，这些变化在时间轴上逐渐累积后，最终会呈现出怎样的整体状态。

为此，他们规定了一个“可接受范围” $[L,R]$。如果从某一天开始，顺着时间向后，将这段时间里每天的变化不断累加进去，在终点处所呈现出的整体结果仍然落在这个范围之内，那么这一整段时间就被认为是“稳定”的。

现在，这份长度为 $n$ 的记录交到了你的手中。你需要从中找出所有这样的连续时间段：它们在经历了从起点到终点的逐步累积之后，最终状态恰好没有越出那道界限。

请你计算，这样的时间段共有多少个。

输入格式

第一行输入三个正整数 $n$ 、 $L$ 和 $R$，表示天数和安全区间。

第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个天的状态偏移量。

输出格式

输出一个整数代表满足条件的区间数目。

样例1

3 -1 2
1 -2 3

4

样例1 解释

我们从不同的起点出发，观察状态如何"逐步变化"：

从第 1 天开始：

第 1 天结束时，状态为 1，在范围内 ✔

第 2 天结束时，状态由 1 变为 -1，仍在范围内 ✔

第 3 天结束时，状态由 -1 变为 2，仍在范围内 ✔

从第 2 天开始：

第 2 天结束时，状态为 -2，不在范围内 ✘

第 3 天结束时，状态由 -2 变为 1，回到范围内 ✔

从第 3 天开始：

第 3 天结束时，状态为 3，不在范围内 ✘

因此共有 4 段满足条件。

样例 2

见选手目录下的 $\texttt{range/range2.in}$ 和 $\texttt{range/range2.ans}$。

该测试用例满足测试点 $3\sim 6$ 的约束条件。

样例 3

见选手目录下的 $\texttt{range/range3.in}$ 和 $\texttt{range/range3.ans}$。

该测试用例满足测试点 $7\sim 10$ 的约束条件。

数据范围

特殊性质 A：保证序列 $a_1, a_2, \dots, a_n$ 均为正整数。

特殊性质 B：$L = R$。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$-10^9 \le L \le R \le 10^9$，$-10^9 \le a_i \le 10^9$。

点击下载大样例