题目描述

墨墨突然对等式很感兴趣，他正在研究 $\sum_{i=1}^{n}{a_ix_i}=b$ 存在非负整数解的条件，他要求你编写一个程序，给定 $n,\{a_n\},l,r$，求出有多少 $b\in[l,r]$ 可以使等式存在非负整数解。

输入格式

第一行三个整数 $n,l,r$。

第二行 $n$ 个整数 $\{a_n\}$。

输出格式

输出一个整数，表示有多少 $b$ 可以使等式存在非负整数解。

样例输入

2 5 10
3 5

样例输出

5

数据规模与约定

对于 $100\%$ 的数据，$n\le12$，$0\le a_i\le5\times10^5$，$1\le l\le r\le10^{12}$。