After their debut in the 2024 Mini Contest 3, the Tarotians now aim to conquer the world! The $N$ Tarotians are standing in a line, and each Tarotian has a power level denoted by $a_i$. To conquer the world, they need to form a team that satisfies the following conditions:

• The team must consist of more than 1 member.
• The team members must be consecutive in the original lineup (i.e., they must form a contiguous subarray of the array $a_i$).
• The team’s World Value must lie between $L$ and $R$ (inclusive).

The World Value for a team of $n$ members, where the $i$-th member has a power level of $b_i$, is calculated as the sum of the synergy between each distinct pair of members. The synergy of a pair of members is defined as the distance between them multiplied by the product of their power levels. Mathematically, $$W(b) = \sum_{i=1}^{n}{ \sum_{j=i+1}^{n} {(j-i) b_i b_j} }.$$ Your task is to determine how many different ways a team can be formed that meets the above conditions.

Input

The first line contains three integers, $N$, $L$, and $R$.
The second line contains $N$ integers, where the $i$-th integer represents $a_i$, the power level of the $i$-th Tarotian.

Output

Output the number of different ways to form a valid team that satisfies the conditions.

Constraints

For all test cases: $1 \le N \le 10^6$, $0 \le a_i \le 10^6$, $0 \le L \le R \le 10^{18}$
Subtask 1 (2%): All $a_i = 0$, $N \le 50$
Subtask 2 (4%): $N \le 50$
Subtask 3 (4%): All $a_i = 1$, $N \le 250$
Subtask 4 (10%): $N \le 250$
Subtask 5 (30%): $N \le 5000$
Subtask 6 (10%): $a_i \le 100$, $N \le 10^5$, $L = R$
Subtask 7 (15%): $L = R$
Subtask 8 (25%): No additional constraints