Description

Xiao Z, who loves Japanese food, often visits the conveyor belt sushi restaurant outside the east gate of his school. There, plates of sushi appear in front of him one by one on a conveyor belt.

Different sushi gives Xiao Z different tastes, so we define that Xiao Z has a satisfaction value for each plate of sushi.

For example, Xiao Z loves salmon, so his satisfaction for a plate of salmon sushi is $10$; Xiao Z thinks tuna has little taste, so his satisfaction for a plate of tuna sushi is only $5$; Xiao Z recently watched the movie Mermaid and felt disgusted by the octopus in it, so his satisfaction for a plate of octopus sashimi is $-100$.

In particular, Xiao Z is a famous foodie and has a habit when eating conveyor belt sushi, which we call “eating nonstop”. Specifically, once he eats a plate of sushi on the conveyor belt, he will immediately eat the sushi after it, until he does not want to eat anymore.

Today, Xiao Z comes to this restaurant again. There will be $N$ plates of sushi passing in front of him in order. Xiao Z’s satisfaction for the $i$-th plate is $a_i$.

Xiao Z can choose which plate to start eating from, and he can also choose which plate to stop at. He wants to know how many different choices there are such that the total satisfaction is not less than $L$ and not greater than $R$.

Note that although this is conveyor belt sushi, we do not treat it as a circular problem, but as a linear one. That is, what Xiao Z can eat is a contiguous subsequence of the input sequence; after the last plate passes by, the first plate will not appear again.

Input Format

The first line contains three positive integers $N, L, R$, representing the number of sushi plates, the lower bound and the upper bound of satisfaction.
The second line contains $N$ integers $a_i$, representing Xiao Z’s satisfaction for each plate of sushi.

Output Format

Output one integer in a single line, representing how many choices make the total satisfaction not less than $L$ and not greater than $R$.

5 5 9
1 2 3 4 5

6

Hint

Constraints.

$1 \le N \le 10^5$
$|a_i| \le 10^5$
$0 \le L, R \le 10^9$

Translated by ChatGPT 5