問題文

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)

入力例 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