墨墨的等式

题目描述

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ 以及区间 $[l,r]$。

对于一个整数 $b$，若存在一组非负整数 $x_1,x_2,\ldots,x_n$，使得

则称 $b$ 是可表示的。

请统计区间 $[l,r]$ 中有多少个整数是可表示的。

输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示区间 $[l,r]$ 中可表示整数的个数。

样例输入 1

2 5 10
3 5

样例输出 1

5

数据范围

对于全部数据：

• $1\le n\le 12$；
• $0\le a_i\le 5\times 10^5$；
• $1\le l\le r\le 10^{12}$。