B. НОД массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив ai длины n. К массиву можно последовательно применить две операции:

  • удалить некоторый подотрезок длины 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.

Примеры
Входные данные
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
Примечание

В первом тесте оптимально удалить число 3 и заплатить за это 1 монету.

Во втором тесте нужно удалить отрезок из чисел [17, 13], а затем уменьшить число 6. Стоимость изменений равна 2·3 + 2 = 8 монетам.