给定长度为 n 的数组 ai。您可以连续对该数组应用两个操作:
- 删除一些长度为 m < n 的子段(连续子序列)并为其支付 m·a 个硬币;
- 将数组的某些元素最多更改 1,并为每次更改支付 b 个硬币。
请注意,每个操作最多可以应用一次(也可能根本不应用),因此您只能删除一个段,并且每个数字最多可以更改(增加或减少)1。另请注意,您不允许删除整个数组。
您的目标是计算您需要花费的最小硬币数量,以使结果数组元素的最大公约数大于 1。
输入
输入的第一行包含整数 n、a 和 b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) - 分别是数组的长度、在第一次操作中删除单个元素的成本和更改元素的成本。
第二行包含 n 个整数 ai (2 ≤ ai ≤ 109) — 数组的元素。
输出
打印单个数字 - 获取数组所需的最小更改成本,使其所有元素的最大公约数大于 1。
示例
输入 #1
3 1 4 4 2 3
输出 #1
1
输入 #2
5 3 2 5 17 13 5 6
输出 #2
8
输入 #3
8 3 4 3 7 5 4 3 12 9 4
输出 #3
13
注意
在第一个示例中,最佳方法是删除数字 3 并为其支付 1 个硬币。
在第二个示例中,您需要删除一段 [17, 13],然后减少数字 6。这些更改的成本等于 2·3 + 2 = 8 个硬币。