#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ld long double
#define lll  __int128
#define dhm std::fixed<<std::setprecision
#define prq priority_queue
using ll = long long;
using ull = unsigned long long;
int T;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
struct Sieve {
	std::vector<int> primes;
	std::vector<int> factor;
	std::vector<bool> is_prime;
	Sieve(int n) : factor(n + 1, -1), is_prime(n + 1, true) {
		is_prime[0] = is_prime[1] = false;
		for (int i = 2; i <= n; i++) {
			if (is_prime[i]) {
				primes.push_back(i);
				factor[i] = i;
			}
			for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; j++) {
				is_prime[i * primes[j]] = false;
				factor[i * primes[j]] = primes[j];
				if (i % primes[j] == 0) break;
			}
		}
	}
} seive(3e5 + 1);
int dp[100005][5];//0 不变 1 变奇数 2 变偶数 3 变1
void solve(){
	memset(dp,0x7f,sizeof(dp));
	int n;
	std::cin>>n;
	std::vector<int>a(n+1);
	for(int i = 1; i <= n ; i ++) {
		std::cin>>a[i];
	}
	if(a[1]==1) {
		dp[1][0]=0;
		dp[1][1]=0;
		dp[1][2]=1;
		dp[1][3]=0;
	}
	else if(a[1]%2==1&&a[1]!=1) {
		dp[1][0]=0;
		dp[1][1]=0;
		dp[1][2]=1;
		dp[1][3]=1;
	}
	else if(a[1]%2==0) {
		dp[1][0]=0;
		dp[1][1]=1;
		dp[1][2]=0;
		dp[1][3]=1;
	}
	for(int i=2;i<=n;i++) {
		if(seive.is_prime[a[i]+a[i-1]]) {
			if(a[i]==1) {
				dp[i][0]=min({dp[i][0],dp[i-1][3],dp[i-1][2],dp[i-1][0]});
				if(a[i-1]==1) {
					dp[i][1]=min({dp[i][1],dp[i-1][2]+1});
					dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][0]+1});
				}
				else {
					dp[i][1]=min({dp[i][1],dp[i-1][0]+1,dp[i-1][2]+1});
					dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][3]+1});
				}
				dp[i][3]=min({dp[i][3],dp[i-1][0],dp[i-1][3],dp[i-1][2]});
			}
			else if(a[i]%2==1) {
				dp[i][0]=min({dp[i][0],dp[i-1][0],dp[i-1][2]});
				dp[i][1]=min({dp[i][1],dp[i-1][0]+1,dp[i-1][2]+1});
				dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][3]+1});
				if(seive.is_prime[a[i-1]+1]) {
					dp[i][3]=min({dp[i][3],dp[i-1][0]+1,dp[i-1][2]+1,dp[i-1][3]+1});
				}
				else {
					dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][3]+1});
				}
			}
			else {
				dp[i][0]=min({dp[i][0],dp[i-1][0],dp[i-1][1]});
				dp[i][2]=min({dp[i][2],dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][3]+1});
				dp[i][1]=min(dp[i][1],dp[i-1][2]+1);
				if(seive.is_prime[a[i]+1]) {
					dp[i][0]=min(dp[i][0],dp[i-1][3]);
				}
				if(a[i-1]==1) dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][0]+1,dp[i-1][3]+1});
				else dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][3]+1});
			}
		}
		else {
			if(a[i-1]==1) {
				dp[i][1]=min(dp[i][1],dp[i-1][2]+1);
				dp[i][2]=min({dp[i][2],dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][3]+1});
				dp[i][3]=min({dp[i][3],dp[i-1][0]+1,dp[i-1][2]+1,dp[i-1][3]+1});
				if(a[i]%2==1) {
					dp[i][0]=min(dp[i][0],dp[i-1][2]);
				}
				else {
					dp[i][0]=min(dp[i][0],dp[i-1][1]);
				}
			}
			else if(a[i-1]%2==1) {
				dp[i][1]=min(dp[i][1],dp[i-1][2]+1);
				dp[i][2]=min({dp[i][2],dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][3]+1});
				if(a[i]==1) {
					dp[i][0]=min({dp[i][0],dp[i-1][2],dp[i-1][3]});
					dp[i][3]=min({dp[i][3],dp[i-1][2],dp[i-1][3]});
				}
				else if(a[i]%2==1) {
					dp[i][0]=min(dp[i][0],dp[i-1][2]);
					dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][3]+1});
				}
				else {
					dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][3]+1});
					if(seive.is_prime[a[i]+1]) dp[i][0]=min({dp[i][0],dp[i-1][1],dp[i-1][3]});
					else dp[i][0]=min(dp[i][0],dp[i-1][1]);
				}
			}
			else {
				dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][3]+1});
				dp[i][1]=min({dp[i][1],dp[i-1][2]+1,dp[i-1][0]+1});
				if(a[i]==1){
					dp[i][0]=min({dp[i][0],dp[i-1][2],dp[i-1][3]});
					dp[i][3]=min({dp[i][3],dp[i-1][2],dp[i-1][3]});
				}
				else if(a[i]%2==1) {
					dp[i][0]=min(dp[i][0],dp[i-1][2]);
					if(seive.is_prime[a[i-1]+1]) dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][0]+1,dp[i-1][3]+1});
					else dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][3]+1});
				}
				else {
					if(seive.is_prime[a[i]+1]) dp[i][0]=min({dp[i][0],dp[i-1][1],dp[i-1][3]});
					else dp[i][0]=min(dp[i][0],dp[i-1][1]);
					if(seive.is_prime[a[i-1]+1]) dp[i][3]=min({dp[i][3],dp[i-1][2]+1,dp[i-1][0]+1});
					else dp[i][3]=min(dp[i][3],dp[i-1][2]+1);
				}
			}
		}
		// cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<" "<<dp[i][3]<<endl;
	}
	cout<<min({dp[n][0],dp[n][1],dp[n][2],dp[n][3]})<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
    T = 1;
	// std::cin>>T;
	while(T --)
	solve();
	return 0;
}