Array GCD

给定一个长为$n$的数组$a_i$，你可以进行以下两个操作： - 对于整个数组，你可以删除一个长度为$m(m<n)$的区间，代价$m\times a$为b，只能操作一次。 - 对于每一个元素，你可以花费$b$元让它$+1$或$-1$，对于每个元素只能操作一次； 求通过上述操作使得剩下的数的最大公约数大于1的最小花费。

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 $ .

The first line of the input contains integers $ n $ , $ a $ and $ b $ ( $ 1<=n<=1000000,0<=a,b<=10^{9} $ ) — 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}<=10^{9} $ ) — elements of the array.

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 $ .

3 1 4
4 2 3

1

5 3 2
5 17 13 5 6

8

8 3 4
3 7 5 4 3 12 9 4

13

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.