Alex tiene un arreglo ~a~ de ~n~ enteros, y dos enteros ~a~ y ~b~. El puede aplicar dos operaciones a este arreglo:

• ~OP1~: remover un subarreglo (subsecuencia continua) de tamaño ~m < n~. El costo de esta operación es de ~m * a~ monedas.

• ~OP2~: cambiar algunos elementos del arreglo por a lo más ~1~. El costo de esta operación es de ~b~ monedas por cada cambio.

Note que cada una de las operaciones pueden ser aplicadas a lo más una vez, por lo que puedes borrar un subarreglo (solo uno) y cambiar algunos elementos (aumentarlos o decrementarlos) en a lo más ~1~. Alex quiere lograr que el mayor divisor común (gcd) del arreglo sea mayor que ~1~ gastando la mínima cantidad de monedas.

Entrada

La primera línea de la entrada contiene los enteros ~n, a~ y ~b (1 \leq n \leq 10^6, 0 \leq a,b \leq 10^9)~. La segunda línea contiene n enteros ~a_1 ,a_2 ,..., a_n~ tal que ~2 \leq a_i \leq 10^9~.

Salida

En una única línea imprima la respuesta del problema.

Ejemplo # 1 de Entrada

3 1 4
4 2 3

Ejemplo # 1 de Salida

1

El conjunto de operaciones puesde ser ~{}, {OP1}, {OP2}, {OP1, OP2}~, el costo de ~OP2~ es ~b~ * la cantidad de elementos que eligió para aumentar o decrementar en ~1~.

Ejemplo # 2 de Entrada

5 3 2
5 17 13 5 6

Ejemplo # 2 de Salida

8

Ejemplo # 3 de Entrada

8 3 4
3 7 5 4 3 12 9 4

Ejemplo # 3 de Salida

13