#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
int n;
bool FLAG=0;
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b,a%b);
}
void fun(int idx, int t){
if(idx==n){
int g=0;
for(int i=0;i<n;i++){
g=gcd(a[i],g);
}
if(g==1)FLAG=1;
return;
}
for(int i=0;i<=t;i++){
a[idx]+=i;
fun(idx+1,t-i);
a[idx]-=i;
}
}
bool dude(int d, int br) {
if(d == n) {
int e = 0;
for(int i = 0; i <n; i++) {
e = gcd(e,a[i]);
}
if(e == 1) {
return 1;
}
return 0;
}
for(int i = 0; i <= br; i++) {
a[d]+=i;
if(dude(d+1,br-i)) {
return true;
}
a[d]-=i;
}
return false;
}
signed main(){
cin>>n;
int g=0;
for(int i=0;i<n;i++){
cin>>a[i];
g=gcd(a[i],g);
}
if(g==1){
cout<<0;
return 0;
}
if(n>15){
cout<<1;
return 0;
}
for(int i=0;i<1000;i++){
// fun(0,i);
if(dude(0,i)) {
cout << i;
return 0;
}
}
}
