#include<iostream>
		#include<queue>
		#include<map>
		#include<set>
		#include<vector>
		#include<algorithm>
		#include<deque>
		#include<cctype>
		#include<string.h>
		#include<math.h>
		#include<time.h>
		#include<random>
		#include<stack>
		#include<string>
		#define ll                        long long 
		#define lowbit(x) (x & -x)
		#define endl "\n"
		using namespace std;
		mt19937 rnd(time(0));
		const ll mod=1e9+7;
		ll ksm(ll x,ll y)
		{
			ll ans=1;
			while(y)
			{
				if(y&1)
				{
					ans=ans%mod*(x%mod)%mod;
				}
				x=x%mod*(x%mod)%mod;
				y>>=1;
			}
			return ans%mod%mod;
		}
		ll gcd(ll x, ll y)
		{
			if (y == 0)
				return x;
			else
				return gcd(y, x % y);
		}
		void fio()
		{
			ios::sync_with_stdio(0);
			cin.tie(0);
			cout.tie(0);
		}
		bool st[500000];
		ll zs[4500000];
		ll cn=0;
		void ola(ll x)
		{
			for(ll i=2;i<=x;i++)
			{
				if(!st[i])cn++,zs[cn]=i;
				for(ll j=1;zs[j]<=x/i;j++)
				{
					st[i*zs[j]]=1;
					if(i%zs[j]==0)break;
				}
			}
		}
		ll a[325000];
		ll dp[325000][4];//变1,变偶,不为1的奇,不变.0 1 2 3 
		map<ll,ll>mp;
		int main()
		{
			fio();
			ola(200005);
			ll n;
			cin>>n;
			for(ll i=1;i<=cn;i++)
			{
				mp[zs[i]]=1;
			}
			for(ll i=1;i<=n;i++)cin>>a[i];
			for(ll i=1;i<=n;i++)
			{ 
				dp[i][0]=dp[i][1]=dp[i][2]=i;
				dp[i][3]=i-1;
				if(i>=2)
				{ 
					if(mp[a[i-1]+a[i]])dp[i][3]=min(dp[i-1][3],dp[i][3]);
					if(mp[1+a[i]])dp[i][3]=min(dp[i][3],dp[i-1][0]);
					if(mp[a[i-1]+1])dp[i][0]=min(dp[i][0],dp[i-1][3]+1);
					dp[i][0]=min({dp[i][0],dp[i-1][0]+1});
					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});
					if(a[i-1]==1)dp[i][0]=min(dp[i][0],dp[i-1][3]+1),dp[i][1]=min(dp[i][1],dp[i-1][3]+1);
					else if(a[i-1]%2==0)dp[i][2]=min(dp[i][2],dp[i-1][3]+1);
					else dp[i][1]=min(dp[i][1],dp[i-1][3]+1);
					if(a[i]==1)dp[i][0]=dp[i][3]=min({dp[i][3],dp[i][0],dp[i-1][0],dp[i-1][1]});
					else if(a[i]%2==0)dp[i][3]=min(dp[i][3],dp[i-1][2]);
					else  dp[i][3]=min(dp[i][3],dp[i-1][1]);
				}
			}
			cout<<min({dp[n][0],dp[n][1],dp[n][2],dp[n][3]})<<endl;
		}