#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,a[300001],f[300001],b[300001],mi=1e18;

signed main(){
ios::sync_with_stdio(false); cin.tie(0);

b[1]=1;
for (int i=2;i<=300000;++i) if (!b[i]) for (int j=i+i;j<=300000;j+=i) b[j]=1;

cin>>n;
for (int i=1;i<=n;++i) cin>>a[i];
for (int i=1;i<=n;++i){
f[i]=i-1;
if (i>=2 && !b[a[i]+a[i-1]]) f[i]=min(f[i],f[i-1]);
if (i>=3 && (abs(a[i]-a[i-2])%2==0 || (!b[a[i]+1] && !b[a[i-2]+1]))) f[i]=min(f[i],f[i-2]+1);
if (i>=4 && (abs(a[i]-a[i-3])%2==1 || a[i]==1 || a[i-3]==1 || (!b[a[i]+1] && !b[a[i-2]+1]))) f[i]=min(f[i],f[i-3]+2);
if (i>=5 && (abs(a[i]-a[i-4])%2==0 || !b[a[i]+1] || !b[a[i-4]+1])) f[i]=min(f[i],f[i-4]+3);
f[i]=min(f[i],mi+i-1);
if (i>=5) mi=min(mi,f[i-4]-(i-4));
}

int ans=1e18;
for (int i=1;i<=n;++i) ans=min(ans,f[i]+(n-i));
cout<<ans<<'\n';

return 0;
}