#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
i64 mul(i64 a, i64 b, i64 m) {
    return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n) { // Miller-Rabin
    if (n < 2) return false;
    static constexpr int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (int p : B) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    i64 m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p : B) {
        i64 t = m, a = power(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1) {
            a = mul(a, a, n);
            t *= 2;
        } 
        if (a != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int dp[n][4] {};
	memset(dp, 0x3f, sizeof(dp));
	if (a[0] == 1) dp[0][3] = 0;
	dp[0][0] = 0;
	dp[0][1] = dp[0][2] = 1;
	for (int i = 1; i <= n; i++) {
		if (isprime(a[i] + a[i - 1])) {
			dp[i][0] = min(dp[i][0], dp[i - 1][0]);
		}
		if (a[i] % 2) dp[i][0] = min(dp[i][0], dp[i - 1][2]);
		else dp[i][0] = min(dp[i][0], dp[i - 1][1]);
		if (a[i] == 1) {
			dp[i][0] = min(dp[i][0], dp[i - 1][3]);
			dp[i][0] = min(dp[i][0], dp[i - 1][2]);
			dp[i][3] = min(dp[i][3], dp[i - 1][3]);
			dp[i][3] = min(dp[i][3], dp[i - 1][2]);
			if (isprime(a[i - 1] + 1)) {
				dp[i][3] = min(dp[i][3], dp[i - 1][0]);
			}
		} else {
			dp[i][3] = min(dp[i][3], dp[i - 1][3] + 1);
			dp[i][3] = min(dp[i][3], dp[i - 1][2] + 1);
			if (isprime(a[i - 1] + 1)) {
				dp[i][3] = min(dp[i][3], dp[i - 1][0] + 1);
			}
		}
		if (a[i - 1] % 2) {
			dp[i][2] = min(dp[i][2], dp[i - 1][0] + 1);
		} else {
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
		}
		dp[i][2] = min(dp[i][2], dp[i - 1][1] + 1);
		dp[i][1] = min(dp[i][1], dp[i - 1][2] + 1);
		dp[i][2] = min(dp[i][2], dp[i - 1][3] + 1);
	}
	cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]}) << '\n';
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int t = 1; 
	// cin >> t;
	while(t--) solve();
	return 0;
}