You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacent elements from a, say x and y, and replace one of them with gcd(x, y), where gcd denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).

What is the minimum number of operations you need to make all of the elements equal to 1?

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements in the array.

The second line contains n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

Output

Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.

Examples

Input

5
2 2 3 4 6


Output

5


Input

4
2 4 6 8


Output

-1


Input

3
2 6 9


Output

4

Note

In the first sample you can turn all numbers to 1 using the following 5 moves:

  * [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]



We can prove that in this case it is not possible to make all numbers one using less than 5 moves.
#include <bits/stdc++.h>
using namespace std;
static const int _ = []() {
  ios::sync_with_stdio(false);
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  return 0;
}();
template <class T>
inline vector<T> rv(long long n) {
  vector<T> v(n);
  for (long long i = 0; i < (n); i++) cin >> v[i];
  return v;
}
template <class T>
inline void pv(const vector<T>& v) {
  for (long long i = 0; i < (v.size()); i++) cout << v[i] << " ";
  cout << endl;
}
template <class T>
inline void amax(T& a, const T& b) {
  if (a < b) a = b;
}
template <class T>
inline void amin(T& a, const T& b) {
  if (a > b) a = b;
}
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
struct Rd {
  template <typename T>
  Rd& operator>>(T& n) {
    cin >> n;
    return *this;
  }
  template <typename T>
  Rd& operator>>(vector<T>& v) {
    for (long long i = 0; i < v.size(); i++) {
      cin >> v[i];
    }
    return *this;
  }
  template <typename T, typename U>
  Rd& operator>>(vector<pair<T, U>>& v) {
    for (long long i = 0; i < v.size(); i++) {
      cin >> v[i].first >> v[i].second;
    }
    return *this;
  }
  template <typename T>
  Rd& operator>>(vector<vector<T>>& v) {
    for (long long i = 0; i < v.size(); i++) {
      for (long long j = 0; j < v[i].size(); j++) {
        cin >> v[i][j];
      }
    }
    return *this;
  }
} rd;
long long GCD(long long a, long long b) {
  while (b) {
    long long r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int main(int argc, char** argv) {
  long long n;
  rd >> n;
  vector<long long> a(n);
  rd >> a;
  long long ans = 0, acc = a[0], k = -1, bk = INT_MAX, ones = 0;
  for (long long i = 0; i < (n); i++) {
    if (a[i] == 1) ones++;
  }
  if (ones) {
    return cout << (n - ones) << endl, 0;
  }
  for (long long i = 0; i < (n); i++) {
    if (i > 0) {
      long long x = GCD(a[i - 1], a[i]);
      if (x == 1) {
        return cout << n << endl, 0;
      }
    }
    if (i < n - 1) {
      long long y = GCD(a[i], a[i + 1]);
      if (y == 1) {
        return cout << n << endl, 0;
      }
    }
    acc = GCD(acc, a[i]);
    if (acc == 1) {
      long long z = a[i], j = i;
      while (z != 1) {
        z = GCD(z, a[j--]);
      }
      bk = min(bk, i - j - 2);
      acc = a[i];
    }
  }
  if (acc > 1 && bk == INT_MAX) {
    return cout << -1 << endl, 0;
  }
  cout << (n + bk) << endl;
  return 0;
}
