output_description: Print the minimum number of operations required to achieve the objective.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 x_2 ... x_N
attempt: #include <bits/stdc++.h>
  
  using namespace std;
  typedef long long ll;
  const int MAXN = 1000100;
  
  #define rep(i, a, b) for(int i = a; i < (b); ++i)
  #define trav(a, x) for(auto& a : x)
  #define all(x) begin(x), end(x)
  #define sz(x) (int)(x).size()
  typedef long long ll;
  typedef pair<int, int> pii;
  typedef vector<int> vi;
  
  int N;
  int arr[MAXN];
   
  struct Dinic {
      struct Edge {
          int to, rev;
          ll c, f;
      };
      vi lvl, ptr, q;
      vector<vector<Edge>> adj;
      Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
      void addEdge(int a, int b, ll c, int rcap = 0) {
          adj[a].push_back({b, sz(adj[b]), c, 0});
          adj[b].push_back({a, sz(adj[a]) - 1, rcap, 0});
      }
      ll dfs(int v, int t, ll f) {
          if (v == t || !f) return f;
          for (int& i = ptr[v]; i < sz(adj[v]); i++) {
              Edge& e = adj[v][i];
              if (lvl[e.to] == lvl[v] + 1)
                  if (ll p = dfs(e.to, t, min(f, e.c - e.f))) {
                      e.f += p, adj[e.to][e.rev].f -= p;
                      return p;
                  }
          }
          return 0;
      }
      ll calc(int s, int t) {
          ll flow = 0; q[0] = s;
          rep(L,0,31) do { // 'int L=30' maybe faster for random data
              lvl = ptr = vi(sz(q));
              int qi = 0, qe = lvl[s] = 1;
              while (qi < qe && !lvl[t]) {
                  int v = q[qi++];
                  trav(e, adj[v])
                      if (!lvl[e.to] && (e.c - e.f) >> (30 - L))
                          q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
              }
              while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
          } while (lvl[t]);
          return flow;
      }
  };
  
  bool pr (int x)
  {
      for (int i = 2; i * i <= x; i++)
          if (x % i == 0) return false;
      return true;
  }
  
  int main()
  {
      ios_base::sync_with_stdio(0);
  
      cin >> N;
      for (int i = 0; i < N; i++)
          cin >> arr[i];
      vector <int> v;
      for (int i = 0; i < N; i++)
      {
          if (i == 0 || arr[i-1] + 1 < arr[i])
              v.push_back(arr[i]);
          if (i == N - 1 || arr[i+1] - 1 > arr[i])
              v.push_back(arr[i]+1);
      }
  
      int m = v.size();
      Dinic d (m + 2);
      int ne = 0, no = 0;
      for (int i = 0; i < m; i++)
      {
          if (v[i] % 2 == 0)
          {
              d.addEdge (m, i, 1);
              ne++;
          }
          else
          {
              d.addEdge (i, m + 1, 1);
              no++;
          }
      }
      for (int i = 0; i < m; i++)
          for (int j = 0; j < m; j++)
          {
              if (v[i] % 2 == 0 && v[j] % 2 == 1)
              {
                  if (pr (abs (i - j)))
                      d.addEdge (i, j, 1);
              }
          }
  
      int r = d.calc (m, m + 1);
  
      int res = r;
      ne -= r;
      no -= r;
      res += 2 * (ne / 2 + no / 2);
      res += 3 * (ne % 2 + no % 2);
      cout << res << "\n";
  }
problem_description: Statement
  
  There are infinitely many cards, numbered 1, 2, 3, ... Initially, Cards x_1,
  x_2, ..., x_N are face up, and the others are face down.
  
  Snuke can perform the following operation repeatedly:
  
    * Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.
  
  Snuke's objective is to have all the cards face down. Find the minimum number
  of operations required to achieve the objective.
samples: [{"input": "2\n    4 5", "output": "2\n    \n\nBelow is one way to achieve the objective in two operations:\n\n  * Select p = 5 and flip Cards 1, 2, 3, 4 and 5.\n  * Select p = 3 and flip Cards 1, 2 and 3.\n\n* * *"}, {"input": "9\n    1 2 3 4 5 6 7 8 9", "output": "3\n    \n\nBelow is one way to achieve the objective in three operations:\n\n  * Select p = 3 and flip Cards 1, 2 and 3.\n  * Select p = 3 and flip Cards 4, 5 and 6.\n  * Select p = 3 and flip Cards 7, 8 and 9.\n\n* * *"}, {"input": "2\n    1 10000000", "output": "4"}]