#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define M 2000005
int n,a[N];
int pri[M],vis[M],f[N][4];
/* 0 不变，1 变为 1，2 变为偶数，3 变为奇数*/
void upd(int &x,int y){x=min(x,y);}
int main(){
	for(int i=2;i<M;i++){
		if(!vis[i])pri[++pri[0]]=i;
		for(int j=1;pri[j]*i<M&&j<=pri[0];j++){
			vis[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	f[1][0]=0;f[1][1]=f[1][2]=f[1][3]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<4;j++)f[i][j]=0x3f3f3f3f;
		if(!vis[a[i-1]+a[i]])upd(f[i][0],f[i-1][0]);
		if(a[i]==1)upd(f[i][0],f[i-1][1]);
		if(a[i]&1)upd(f[i][0],f[i-1][2]);
		if(~a[i]&1)upd(f[i][0],f[i-1][3]);
		/*------------------------------*/
		if(!vis[a[i-1]+1])upd(f[i][1],f[i-1][0]);
		upd(f[i][1],f[i-1][1]);
		upd(f[i][1],f[i-1][2]);
		++f[i][1];
		/*------------------------------*/
		if(a[i-1]&1)upd(f[i][2],f[i-1][0]);
		upd(f[i][2],f[i-1][1]);
		upd(f[i][2],f[i-1][3]);
		++f[i][2];
		/*------------------------------*/
		if(~a[i-1]&1)upd(f[i][3],f[i-1][0]);
		upd(f[i][3],f[i-1][2]);
		++f[i][3];
	}
	printf("%d\n",min({f[n][0],f[n][1],f[n][2],f[n][3]}));
}