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

using LL=long long;
const int N=3e5+10;
const int M=N*2;
const LL INF=1e18;
const int mod=998244353;
int n,m;
int prime[N], num;
int vis[N];

void find_prime(int n) {
    int i, j;
    for (i = 2; i < n; i++) {
        if (!vis[i])prime[++num] = i;
        for (j = 1; j <= num && prime[j] <= n / i; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)break;
        }
    }
}
void solve() {
    find_prime(200010);
    cin>>n;
    vector<int>a(n+1);
    vector<vector<int>>dp(n+1,vector<int>(4,-1));
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    //不变
    //改为1
    //改为偶数
    //改为>1的奇数
    dp[1][0]=0,dp[1][1]=0,dp[1][2]=0,dp[1][3]=0;
    if(a[1]!=1)dp[1][1]=1;
    if(a[1]%2!=0)dp[1][2]=1;
    if(a[1]%2!=1||a[1]==1)dp[1][3]=1;
    auto change=[](int &x,int y) {
        if(y==-1)return;
        x==-1?x=y:x=min(x,y);
    };
    for(int i=2;i<=n;i++) {
        //不变
        if(dp[i-1][0]!=-1) {
            if(!vis[a[i-1]+a[i]]) {
                change(dp[i][0],dp[i-1][0]);
            }
        }
        if(dp[i-1][1]!=-1) {
            if(!vis[1+a[i]]) {
                change(dp[i][0],dp[i-1][1]);
            }
        }
        if(dp[i-1][2]!=-1) {
            if(a[i]&1) {
                change(dp[i][0],dp[i-1][2]);
            }
        }
        if(dp[i-1][3]!=-1) {
            if(a[i]%2==0) {
                change(dp[i][0],dp[i-1][3]);
            }
        }

        //改为1
        if (dp[i - 1][0] != -1) {
            if (!vis[1 + a[i - 1]]) {
                change(dp[i][1], dp[i-1][0]+(a[i]!=1));
            }
        }
        if(dp[i-1][1]!=-1) {
            change(dp[i][1],dp[i-1][1]+(a[i]!=1));
        }
        if(dp[i-1][2]!=-1) {
            change(dp[i][1],dp[i-1][2]+(a[i]!=1));
        }

        //改为偶数
        if(dp[i-1][0]!=-1) {
            if(a[i-1]&1) {
                change(dp[i][2],dp[i-1][0]+1);
            }
        }
        if(dp[i-1][1]!=-1) {
            change(dp[i][2],dp[i-1][1]+1);
        }
        if(dp[i-1][3]!=-1) {
            change(dp[i][2],dp[i-1][3]+1);
        }

        //改为>1奇数
        if(a[i-1]%2==0&&dp[i-1][0]!=-1) {
            change(dp[i][3],dp[i-1][0]+1);
        }
        if(dp[i-1][2]!=-1) {
            change(dp[i][3],dp[i-1][2]+1);
        }

    }
    int res=-1;
    change(res,dp[n][0]);
    change(res,dp[n][1]);
    change(res,dp[n][2]);
    change(res,dp[n][3]);
    cout<<res<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    while(T--)solve();
    return 0;
}