Вам дан массив a длиной n, вы можете выполнять определенные операции над ним. Каждая операция выгладит следующим образом: выберите два соседних элемента из a, пусть это будут x и y, и замените один из них величиной gcd(x, y), где gcd обозначает наибольший общий делитель.
Какое минимальное число операций необходимо, чтобы сделать все элементы массива равными 1?
Выходные данные
Выведите -1, если невозможно сделать все элементы массива равными 1. Иначе выведите минимальное число операций, необходимых для того, чтобы сделать все числа равными 1.
Примечание
В первом примере можно изменить все числа на 1, используя следующие 5 шагов:
- [2, 2, 3, 4, 6].
- [2, 1, 3, 4, 6]
- [2, 1, 3, 1, 6]
- [2, 1, 1, 1, 6]
- [1, 1, 1, 1, 6]
- [1, 1, 1, 1, 1]
Можно доказать, что нельзя достичь того же меньше, чем за 5 операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2 3 4 6
|
5
|
|
2
|
4
2 4 6 8
|
-1
|
|
3
|
3
2 6 9
|
4
|