#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define pii pair<int,int>
vector<int> prime;
#define maxn 1000005
int dp[maxn][2];//改成奇或偶
int dp1[maxn];//为1
int dp2[maxn];//不改
int ok[maxn];
int a[maxn];
int g[maxn];//奇偶

void sieve(int x){
    vector<int> arr(x+1);
    for(int i=2;i<=x;i++) {
        if(!arr[i]){
            prime.push_back(i);
            ok[i]=1;
        } 
        for(auto it:prime) {
            if(i*it>x)break;
            arr[i*it]=1;
            if(i%it==0)break;
        }
    }
}

void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        g[i]=(a[i]&1);
    }
    dp[1][0]=dp[1][1]=1;
    dp1[1]=(a[1]!=1);
    dp2[1]=0;
    for(int i=2;i<=n;i++){
        //改成奇 偶
        dp[i][1]=dp[i-1][0]+1;
        if(g[i-1]==0)dp[i][1]=min(dp[i][1],dp2[i-1]+1);
        dp[i][0]=dp[i-1][1]+1;
        if(g[i-1]==1)dp[i][0]=min(dp[i][0],dp2[i-1]+1);
        dp[i][0]=min(dp[i][0],dp1[i-1]+1);

        //这位为1
        dp1[i]=dp1[i-1];
        if(ok[a[i-1]+1])dp1[i]=min(dp1[i],dp2[i-1]);
        dp1[i]=min(dp1[i],dp[i][0]);
        
        dp1[i]+=(a[i]!=1);

        //不改
        dp2[i]=dp[i-1][g[i]^1];
        if(ok[a[i]+1])dp2[i]=min(dp2[i],dp1[i]);
        if(ok[a[i]+a[i-1]])dp2[i]=min(dp2[i],dp2[i-1]);
        //cout<<"i="<<i<<'\n';
        //cout<<"改成奇数 偶数="<<' '<<dp[i][0]<<' '<<dp[i][1]<<'\n';
        //cout<<"1="<<dp1[i]<<'\n';
        //cout<<"不改="<<dp2[i]<<'\n'<<'\n';
    }
    int ans=min({dp[n][0],dp[n][1],dp1[n],dp2[n]});
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    sieve(1e6);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}