AT_utpc2023_j Japanese Gift Money

现在有 $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$ 日元以下的金额中，有多少个是**好金额**。

输入由一行组成，格式如下： > $N\ L\ R\ A_1\ A_2\ \ldots\ A_N$

输出一个整数，表示答案。

### 样例解释 1 例如，如果放入三张 10 日元纸币，则可以得到 $30$ 日元，这是 $30$ 日元的**好放法**，因此 $30$ 日元是**好金额**。 另一方面，$20$ 日元的**好放法**不存在，因此 $20$ 日元不是**好金额**。 从 $21, 23, 25, 26, 27, 28, 29, 30$ 共 $8$ 个金额是**好金额**，答案是 $8$。 ### 数据范围 - 所有输入均为整数。 - $1 \leq N \leq 60$ - $1 \leq L \leq R \leq 10^{18}$ - $1 = A_1 < A_2 < \cdots < A_N \leq 10^{18}$ - 对于 $1 \leq i \leq N-1$，有 $A_{i+1}$ 是 $A_i$ 的倍数。 由 ChatGPT 5 翻译