Вам дан массив ai длины n. К массиву можно последовательно применить две операции:
- удалить некоторый подотрезок длины m < n, заплатив за это m·a монет;
- изменить некоторые элементы массива не более чем на 1, заплатив за каждое изменение b монет.
Обратите внимание, что каждую операцию можно выполнить только по одному разу (а можно и не выполнять вовсе), то есть удалить можно только один отрезок и каждое число можно изменить (увеличить или уменьшить) не более чем на 1. Дополнительно обратите внимание, что, выполняя первую операцию, мы не можем удалить весь массив.
Какое минимальное количество монет потребуется потратить, чтобы получить массив, наибольший общий делитель элементов которого больше 1?
Выходные данные
Выведите единственное целое число — минимальную стоимость изменений, необходимых для получения массива, наибольший общий делитель элементов которого больше 1.
Примечание
В первом тесте оптимально удалить число 3 и заплатить за это 1 монету.
Во втором тесте нужно удалить отрезок из чисел [17, 13], а затем уменьшить число 6. Стоимость изменений равна 2·3 + 2 = 8 монетам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 4
4 2 3
|
1
|
|
2
|
5 3 2
5 17 13 5 6
|
8
|
|
3
|
8 3 4
3 7 5 4 3 12 9 4
|
13
|