891A - Pride - CodeForces Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define ll long long
using namespace std;

void solve() {
    int n,i,j,ans=4004,ones=0;
    cin >> n;
    vector<int> a(n);
    for(i=0;i<n;i++) {
        cin >> a[i];
        if(a[i]==1) ones++;
    }
    if(ones==n) {
        cout << 0 << endl;
        return;
    }
    for(i=0;i<n-1;i++) {
        int check=a[i+1];
        for(j=i+1;j<n;j++) {
            check=gcd(check,a[j]);
            if(gcd(a[i],check)==1) ans=min(ans,j-i+n-1);
        }
    }
    if(ans==4004) cout << -1 << endl;
    else cout << ans-ones << endl;
}

int main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int t=1;
    // cin >> t;
    while(t--) {
        solve();
    }
}