//code by Emissary
#include<bits/stdc++.h>

#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 5e5+5;
const int mod = 998244353;
//const int mod = 1e9+7;

int f[MAXN][10];
//不变, 奇、偶、1
int n, a[MAXN], pri[MAXN], cnt;

bool vis[MAXN];

inline void getprime(int lim){
	for(int i=2;i<=lim;++i){
		if(!vis[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt && pri[j]*i<=lim;++j){
			vis[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}

signed main(){
	getprime(int(3e5)+1);
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	memset(f,127/3,sizeof f);
	f[1][1]=0; f[1][2]=f[1][3]=f[1][4]=1;
	for(int i=2;i<=n;++i){
		if(vis[a[i]+1]==0) f[i][1]=min(f[i][1],f[i-1][4]);
		if(vis[a[i-1]+1]==0) f[i][4]=min(f[i-1][1]+1,f[i][4]);
		f[i][4]=min(f[i][4],f[i-1][4]+(a[i]!=1));
		f[i][2]=min(f[i][2],f[i-1][3]+1);
		f[i][3]=min(f[i][3],f[i-1][2]+1);
		f[i][3]=min(f[i][3],f[i-1][4]+1);
		if(a[i-1]%2==0) f[i][2]=min(f[i][2],f[i-1][1]+1);
		else f[i][3]=min(f[i][3],f[i-1][1]+1);
		if(a[i]%2==0) f[i][1]=min(f[i][1],f[i-1][2]);
		else f[i][1]=min(f[i][1],f[i-1][3]);
		if(vis[a[i]+a[i-1]]==0) f[i][1]=min(f[i][1],f[i-1][1]);
		//cerr << i << ' ' << f[i][1] << ' ' << f[i][2] << ' ' << f[i][3] << ' ' << f[i][4] << endl;
	}
	int ans=1e9;
	for(int i=1;i<=4;++i) ans=min(ans,f[n][i]);
	eprint(ans);
	return 0;
}