Q. Another Floors Problem
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. How many numbers between $$$l$$$ and $$$r$$$ $$$(1\le l \le r\le10^{18})$$$ can be expressed in the form $$$\displaystyle\sum_{i=1}^{n}\lfloor a_ix\rfloor$$$, where $$$x$$$ is a real number, and $$$\lfloor y\rfloor$$$ denotes greatest integer less than or equal to $$$y$$$?

Input

The first line consists of three integers $$$n$$$, $$$l$$$, and $$$r$$$ $$$(1 \leq n \leq 10^{5}, 1 \le l \le r \le 10^{18})$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^5)$$$.

The first $$$5$$$ test cases (not including the sample) satisfy $$$n \le 100$$$, $$$a_i \le 1000$$$, $$$l \le r \le 1000$$$.

The next $$$10$$$ test cases satisfy $$$n \le 10^5$$$, $$$l \le r \le 10^9$$$.

The last $$$5$$$ test cases do not have any extra constraints.

Output

Print a single integer $$$-$$$ the number of reachable integers in the range $$$[l, r]$$$.

Example
Input
2 2 8
2 3
Output
6
Note

$$$x=\frac{1}{2}$$$ gives a sum of $$$2$$$.

$$$x=\frac{2}{3}$$$ gives a sum of $$$3$$$.

$$$x=1$$$ gives a sum of $$$5$$$.

$$$x=\frac{4}{3}$$$ gives a sum of $$$6$$$.

$$$x=\frac{3}{2}$$$ gives a sum of $$$7$$$.

$$$x=\frac{5}{3}$$$ gives a sum of $$$8$$$.

It can be shown that it is impossible to attain a sum of $$$4$$$.

Idea: thehunterjames

Preparation: thehunterjames

Occurrences: Advanced, 7