K. Candies
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard 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$$$.

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