A. Гордыня
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

Выведите -1, если невозможно сделать все элементы массива равными 1. Иначе выведите минимальное число операций, необходимых для того, чтобы сделать все числа равными 1.

Примеры
Входные данные
5
2 2 3 4 6
Выходные данные
5
Входные данные
4
2 4 6 8
Выходные данные
-1
Входные данные
3
2 6 9
Выходные данные
4
Примечание

В первом примере можно изменить все числа на 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 операций.