5729. 你须偿还

单点时限: 1.0 sec

内存限制: 512 MB

莫斯提马躲进了城镇。菲亚梅塔正在追杀她。

城镇里有$n(1 \leq n \leq 2\times 10^5)$座修道院排成一行,第$i$座修道院的高度为$a_i(|a_i| \leq 10^9)$。

菲亚梅塔不想花时间寻找莫斯提马,她设定了两个参数$l, r(-10^{15} \leq l \leq r \leq 10^{15})$。

一段位置连续的修道院的高度之和在$[l,r]$之内时,菲亚梅塔会直接来一发你须偿还。菲亚梅塔想知道自己一共会发射多少发你须偿还

形式化地说,求满足$l \leq \sum_{k=i}^{j}a_k \leq r$的二元组$(i,j)$数量。

其中:$ 1 \leq i \leq j \leq n$

输入格式

第一行,三个正整数$n, l, r$。

第二行,$n$个整数$a_i$,表示修道院的高度。

输出格式

输出一个数,表示你的答案。

样例

Input
6 1 5
1 1 4 5 1 4
Output
9
Input
10 -3 5
2 -1 4 -7 4 8 -3 -6 -4 7
Output
32

69 人解决,141 人已尝试。

96 份提交通过,共有 456 份提交。

5.0 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 1 周前.

来源: N/A

题目标签