#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int N=2e5+10;
vector<int>primes(N);
bool st[N];
int cnt;
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int a[N];
void solve () {
    cin>>n;
    vector<vector<int>>dp(n+2,vector<int>(5,1e18));
    for(int i=1;i<=n;i++)cin>>a[i];
    if(!st[a[1]])dp[1][0]=0;
    dp[1][1]=1;
    dp[1][2]=1;
    for(int i=2;i<=n;i++){
        if(a[i]%2==0){
            dp[i][0]=dp[i-1][1];
        }
        else {
            dp[i][0]=dp[i-1][2];
        }
        if(!st[a[i]+a[i-1]]){
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
        }
        if(a[i-1]==1){
            dp[i][1]=min({dp[i-1][0],dp[i-1][2],dp[i-1][1]})+1;
            dp[i][2]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+1;
            continue;
        }
        if(a[i-1]%2==0){
            dp[i][1]=min(dp[i-1][0],dp[i-1][2])+1;
            dp[i][2]=min(dp[i-1][0],dp[i-1][1])+2;
        }
        else{
            dp[i][1]=min(dp[i-1][0],dp[i-1][2])+2;
            dp[i][2]=min(dp[i-1][0],dp[i-1][1])+1;
        }
        
    }
    // for(int i=1;i<=n;i++){
    //     cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
    // }
    cout<<min({dp[n][1],dp[n][0],dp[n][2]})<<endl;
}
signed main () {
    int T = 1; 
    get_primes(200000);
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //cin>>T;
    while (T --) solve ();
    return 0;
}