Олимпиадный тренинг

Задача . A. Гордыня


Вам дан массив a длиной n, вы можете выполнять определенные операции над ним. Каждая операция выгладит следующим образом: выберите два соседних элемента из a, пусть это будут x и y, и замените один из них величиной gcd(x, y), где gcd обозначает наибольший общий делитель.

Какое минимальное число операций необходимо, чтобы сделать все элементы массива равными 1?

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 2000) — количество элементов в массиве.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива.

Выходные данные

Выведите -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
Статистика успешных решений по компиляторам