有 $N$ 种面值的纸币，第 $i$ 种纸币的面值为 $A_i$ 日元。每种纸币你都有 $10^{100}$ 张。已知 $A_1 < A_2 < \dots < A_N$ 成立，且对于每个 $1 \le i \le N - 1$，$A_{i+1}$ 都是 $A_i$ 的倍数。

你打算选择其中一些纸币放入信封中。如果一种放入纸币的方式满足以下条件，则称其为放入 $x$ 日元的“好方法”： 信封中纸币的总金额为 $x$ 日元。 无法从信封中的纸币里选出总金额恰好为 $\frac{x}{2}$ 日元的纸币组合。

此外，如果存在一种放入 $x$ 日元的“好方法”，则称 $x$ 日元为“好金额”。 请计算在 $L$ 日元到 $R$ 日元（包含 $L$ 和 $R$）之间，有多少个“好金额”。

输入格式

输入通过标准输入按以下格式提供：

$N \ L \ R$ $A_1 \ A_2 \ \dots \ A_N$

• 所有输入均为整数。
• $1 \le N \le 60$
• $1 \le L \le R \le 10^{18}$
• $1 = A_1 < A_2 < \dots < A_N \le 10^{18}$
• $A_{i+1}$ 是 $A_i$ 的倍数。（$1 \le i \le N - 1$）

输出格式

在一行中输出答案。

样例

样例输入 1

3 20 30
1 5 10

样例输出 1

8

样例输入 2

8 500007484602844543 985892611352151235
1 1971 151767 10927224 87417792 118975614912 263174060185344 43686893990767104

样例输出 2

483957600323779237

说明

例如，30 日元是一个好金额，因为放入三张 10 日元的纸币是放入 30 日元的一种好方法。 另一方面，20 日元不是一个好金额，因为不存在放入 20 日元的好方法。 在 20 日元到 30 日元之间有 8 个好金额：21, 23, 25, 26, 27, 28, 29, 30 日元。