最大公约数

import java.util.Scanner;

public class Main {
    static final int N = 100010, INF = 0x3f3f3f3f;
    static Node[] tr = new Node[N * 4];
    static int[] a = new int[N];
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            if (a[i] == 1) cnt++;
        }

        if (cnt != 0) {
            System.out.println(n - cnt);
            return;
        }

        build(1, 1, n);
        if (query(1, 1, n, 1, n) != 1) {
            System.out.println(-1);
            return;
        }

        int ans = INF;
        for (int i = 1; i <= n; i++) {
            int l = i, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (query(1, 1, n, i, mid) == 1) r = mid;
                else l = mid + 1;
            }

            if (query(1, 1, n, i, r) == 1) ans = Math.min(ans, n - 1 + r - i);
        }

        System.out.println(ans);
    }

    static int query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tr[u].d;

        int mid = l + r >> 1;
        if (qr <= mid) return query(u * 2, l, mid, ql, qr);
        else if (ql > mid) return query(u * 2 + 1, mid + 1, r, ql, qr);
        else return gcd(query(u * 2, l, mid, ql, qr), query(u * 2 + 1, mid + 1, r, ql, qr));
    }

    static void build(int u, int l, int r) {
        tr[u] = new Node();
        if (l == r) {
            tr[u].d = a[l];
            return;
        }

        int mid = l + r >> 1;
        build(u * 2, l, mid);
        build(u * 2 + 1, mid + 1, r);
        pushup(u);
    }

    static void pushup(int u) {
        tr[u].d = gcd(tr[u * 2].d, tr[u * 2 + 1].d);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static class Node {
        int d;
    }
}