Description

Momo has suddenly become interested in equations. He is studying the condition under which $\sum_{i=1}^n a_ix_i=b$ has a non-negative integer solution. He asks you to write a program: given $n, a_{1\dots n}, l, r$, find how many $b \in [l, r]$ make the equation have a non-negative integer solution.

Input Format

The first line contains three integers $n,l,r$. The second line contains $n$ integers $a_{1\dots n}$.

Output Format

Output one integer on a single line, indicating how many $b \in [l, r]$ make the equation have a non-negative integer solution.

2 5 10
3 5

5

Hint

For $20\%$ of the testdata, $n \le 5$, $r \le 10$. For $40\%$ of the testdata, $n \le 10$, $r \le 10^6$. For $100\%$ of the testdata, $n \le 12$, $0 \le a_i \le 5\times 10^5$, $1 \le l \le r \le 10^{12}$.

Translated by ChatGPT 5