#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]);
for (int j=2;j<=3;++j)
if (i-j>=1 && (abs(a[i]-a[i-j])%2==j%2 || (!b[a[i]+1] && !b[a[i-j]+1]) || a[i]==1 || a[i-j]==1))
f[i]=min(f[i],f[i-j]+j-1);
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;
}