题目描述

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

输入格式

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

第二行 n 个整数 {an​}。

输出格式

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

样例输入

2 5 10
3 5

样例输出

5

数据规模与约定

对于 100% 的数据，n≤12，0≤ai​≤5×105，1≤l≤r≤1012。