406186: GYM102302 K Candies

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Candiestime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Nicoleta received a box of candies from his sister. It has a rectangular shape with dimensions $$$1$$$ x $$$N$$$ and contains $$$N$$$ candies, and each one has a value $$$C_i$$$ of deliciousness.

Sanchola lives with Nicoleta in Revuocnav and he loves to make Nicoleta upset. Sanchola found out about the gift and decided to take a consecutive subsequence of candies from the box when Nicoleta is not looking. The total deliciousness taken by Sanchola should be at least L so that he can enjoy the candies, but not greater than R, to not raise suspicion.

Sanchola needs your help to calculate the number of distinct consecutive subsequences that he can take from Nicoleta.

Two consecutive subsequences $$$C_{l_1} \cdots C_{r_1}$$$ and $$$C_{l_2} \cdots C_{r_2}$$$ are considered equal if and only if they have the same number of candies $$$x$$$ and $$$\forall{k}$$$ $$$C_{l_1 + k} = C_{l_2 + k}, 0 \leq k \lt x$$$.

Input

The first line consists of three integers $$$N$$$ $$$(1 \leq N \leq 5 * 10^{5})$$$, $$$L$$$ and $$$R$$$ $$$(-10^{18} \leq L \leq R \leq 10^{18})$$$ .

The second line contains $$$N$$$ integers $$$C_{1}, C_{2}, \cdots, C_{n}$$$ ($$$-10^{9} \leq a_{i} \leq 10^{9}$$$), indicating the deliciousness of each candy.

Output

Output a single integer - The number of distinct consecutive subsequences whose sum is between $$$L$$$ and $$$R$$$.

ExamplesInput
5 5 10
1 2 3 4 5
Output
7
Input
5 5 10
1 2 3 4 4
Output
6

Source/Category

加入题单

上一题 下一题 算法标签: