CF623B.Array GCD

You are given array a__i of length n. You may consecutively apply two operations to this array:

• remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
• change some elements of the array by at most 1, and pay b coins for each change.

Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.

Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

给你一个长度为 $n$ 的数组 $a_i$。你可以对该数组连续执行以下两种操作：

• 删除一个长度为 $m$（其中 $m < n$）的子段（即连续子序列），并为此支付 $m \cdot a$ 枚硬币；
• 将数组中某些元素的值最多改变 $1$（即每个被修改的元素可增加或减少 $1$），并对每次修改支付 $b$ 枚硬币。

请注意，每种操作最多只能执行一次（也可以完全不执行），因此你至多只能删除一个子段，且每个数至多被修改 $1$。此外，你不允许删除整个数组。

你的目标是计算使最终数组所有元素的最大公约数（GCD）大于 $1$ 所需花费的最少硬币数量。

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.

The second line contains n integers a__i (2 ≤ a__i ≤ 109) — elements of the array.

输入的第一行包含整数 $n$、$a$ 和 $b$（$1 \leq n \leq 1\,000\,000$，$0 \leq a,\,b \leq 10^9$）—— 分别表示数组的长度、第一次操作中移除单个元素的代价，以及修改一个元素的代价。

第二行包含 $n$ 个整数 $a_i$（$2 \leq a_i \leq 10^9$）—— 数组的元素。

Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.

输出一个整数——使得数组中所有元素的最大公约数大于 1 所需的最小修改代价。

In the first sample the optimal way is to remove number 3 and pay 1 coin for it.

In the second sample you need to remove a segment [17, 13] and then decrease number 6. The cost of these changes is equal to 2·3 + 2 = 8 coins.

在第一个样例中，最优方案是删除数字 3，花费 1 枚硬币。

在第二个样例中，你需要删除区间 [17, 13]，然后将数字 6 减小。这些操作的总花费为 $2 \cdot 3 + 2 = 8$ 枚硬币。