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 翻译