← 返回题目列表

Codeforces · 346/C

C. 数字转换 II

中文机器翻译题面 查看原题

给定一个正整数 x1、x2、...、xn 和两个非负整数 a 和 b 的序列。你的任务是将a转变成b。为此,您可以执行以下操作:

- 当前a减1;
- 从当前 a 中减去 mod xi (1 ≤ i ≤ n)。

a mod xi 运算表示取数字 a 除以数字 xi 后的余数。

现在您想知道将 a 转换为 b 所需的最少移动次数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个空格分隔的整数 x1, x2, ..., xn (2 ≤ xi ≤ 109)。第三行包含两个整数 a 和 b (0 ≤ b ≤ a ≤ 109, a - b ≤ 106)。

输出

打印一个整数 - 将数字 a 转换为数字 b 所需的最小移动次数。

示例

输入 #1

3
3 4 5
30 17

输出 #1

6

输入 #2

3
5 6 7
1000 200

输出 #2

206