#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_set>
using namespace std;
const int N=3e5;
unordered_set<int> bp;
vector<int> prime;
bool bl[N];
void init()
{
    bl[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!bl[i]) {prime.push_back(i);bp.insert(i);}
        for(auto c:prime)
        {
            if(i*c>=N) break;
            bl[i*c]=1;
            if(i%c==0) break;
        }
    }
}
int dp[N][2][2],ol[N]; //0 不变
int arr[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    memset(dp,0x3f,sizeof dp);
    memset(ol,0x3f,sizeof ol);

    int n; cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        int fg=arr[i]%2;
        if(i==1) 
        {
            dp[i][1][0]=dp[i][1][1]=1;
            dp[i][0][fg]=0;

            if(arr[i]==1) ol[i]=0;
            else ol[i]=1;
            continue;
        }

        if(bp.count(arr[i]+arr[i-1])) dp[i][0][fg]=min(dp[i-1][0][fg^1],dp[i-1][1][fg^1]);
        else dp[i][0][fg]=dp[i-1][1][fg^1];

        dp[i][0][fg^1]=min(dp[i-1][0][fg],dp[i-1][1][fg])+1;

        if(arr[i]==1) dp[i][0][1]=min(dp[i][0][1],ol[i-1]);
        if(bp.count(arr[i]+1)) dp[i][0][fg]=min(dp[i][0][fg],ol[i-1]);
        

        dp[i][1][fg]=min(dp[i-1][0][fg^1],dp[i-1][1][fg^1])+1;
        dp[i][1][fg^1]=min(dp[i-1][0][fg],dp[i-1][1][fg])+1;

        dp[i][1][0]=min(dp[i][1][0],ol[i-1]+1);

        if(arr[i]==1) 
        {
            int tf=1;
            if(bp.count(arr[i-1]+1)) tf=0;
            ol[i]=min(dp[i-1][1][0],ol[i-1]);
            ol[i]=min(ol[i],ol[i-1]);
            ol[i]=min(ol[i],dp[i-1][0][arr[i-1]%2]+tf);
        }
        else 
        {
            
            int tf=1;
            if(bp.count(arr[i-1]+1)) tf=0;

            ol[i]=min(dp[i-1][1][0],ol[i-1])+1;
            ol[i]=min(ol[i],ol[i-1]+1);
            ol[i]=min(ol[i],dp[i-1][0][arr[i-1]%2]+1+tf);
            // if(i==10)
            // {
            //     cout<<ol[i]<<":::: ";
            //   cout<<dp[i-1][0][arr[i-1]%2]<<"!!\n";
            // }
        }
    
        
        // cout<<i<<" "<<dp[i][0][arr[i]%2]<<'\n';
    }
    int mi=min(dp[n][1][arr[n]%2],dp[n][0][arr[n]%2]);
    mi=min(mi,min(dp[n][1][(arr[n]%2)^1],dp[n][0][(arr[n]%2)^1]));
    mi=min(mi,ol[n]);
    cout<<mi;
 
    
    
}