配点 : 100 点
問題文
N 有几种纸币,i 第几种纸币是 A_i 日元钞票。每种纸币都有 10^{100} 张。在这里 A_1 < A_2 < \cdots < A_N 并且,每 i \: (1 \leq i \leq N - 1) 反对 A_{i+1} 是 您也可以写 A_i 的倍数。 给出了
我们考虑从这些纸币中选择几张放入袋子里。
在将纸币放入袋子的方法中,满足以下条件的方法称为、x 圆的好的放入方式称为。
- 放入袋子的纸币总金额是 x 这是日元。
- 从放入袋子的纸币中选择几张,其总金额为 \dfrac{x}{2} 日元的方法不存在。
另外,x 日元为好的金额意味着x 圆的好的放入方式表示其存在。
L 円以上 R 在不超过日元的金额中,好的金额有多少个,请求出。
制約
- 所有输入均为整数
- 1 \leq N \leq 60
- 1 \leq L \leq R \leq 10^{18}
- 1 = A_1 < A_2 < \cdots < A_N \leq 10^{18}
- A_{i+1} 是 您也可以写 A_i 的倍数 (1 \leq i \leq N - 1)
入力
输入是按以下格式从标准输入给出的。
N L R A_1 A_2 \ldots A_N
出力
答案 请打印除以 1 行输出。
入力例 1
3 20 30 1 5 10
出力例 1
8
例如 第 10 日元钞票 我有 3 如果放入张数为 30 圆的好的放入方式,所以30 日元是好的金额。
一方、20 圆的好的放入方式不存在,所以20 日元是好的金额。 您将收到
21, 23, 25, 26, 27, 28, 29, 30 圆的 8 个是答案。
入力例 2
8 500007484602844543 985892611352151235 1 1971 151767 10927224 87417792 118975614912 263174060185344 43686893990767104
出力例 2
483957600323779237