#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
pair<int, int> T[MAXN];
pair<int, int> A[MAXN];
unordered_map<int, vector<int>> pos;
vector<int> cntm2;
map<pair<int, int>, tuple<int, int, int, int>> DP_cur, DP_prev;
int solution[MAXN];
int lastx = -1;
int lasty = -1;
int lastr = -1;
long long int gcd(long long int x, long long int y, bool nn = true) {
  if ((x == lastx) && (y == lasty)) return lastr;
  if (nn) {
    lastx = x;
    lasty = y;
  }
  if (y == 0) {
    lastr = x;
    return x;
  }
  return gcd(y, x % y, false);
}
void Print() {
  if (DP_prev.count(make_pair(1, 1))) {
    cout << "YES\n";
    int a = 1, b = 1;
    while (a != -1) {
      int eidx = get<0>(DP_prev[make_pair(a, b)]);
      int esol = get<1>(DP_prev[make_pair(a, b)]);
      int na = get<2>(DP_prev[make_pair(a, b)]);
      int nb = get<3>(DP_prev[make_pair(a, b)]);
      auto& o = *(DP_prev.find(make_pair(a, b)));
      solution[eidx] = esol;
      a = na;
      b = nb;
    }
    for (int i = 0; i < n; i++) {
      if (solution[i] == -1)
        cout << rand() % 2 + 1 << " ";
      else
        cout << solution[i] << " ";
    }
    cout << "\n";
    exit(0);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  clock_t t1 = clock();
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> T[i].first;
    T[i].second = i;
  }
  srand(n + T[0].first);
  for (int tries = 0; tries < 100; tries++) {
    {
      clock_t t2 = clock();
      clock_t t = t2 - t1;
      double tx = (double)t / CLOCKS_PER_SEC;
      if (tx >= 0.4) break;
    }
    random_shuffle(T, T + n);
    int x = rand() % n;
    int y;
    do {
      y = rand() % n;
    } while (x == y);
    pos.clear();
    for (int i = 0; i < n; i++) {
      if (i == x) {
        solution[T[i].second] = 1;
        continue;
      }
      if (i == y) {
        solution[T[i].second] = 2;
        continue;
      }
      solution[T[i].second] = -1;
      A[i] = make_pair(gcd(T[i].first, (long long int)T[x].first * T[y].first),
                       T[i].second);
      pos[A[i].first].push_back(T[i].second);
    }
    x = T[x].first;
    y = T[y].first;
    for (const pair<int, vector<int>>& z : pos)
      if (z.second.size() >= 2) {
        x = gcd(x, z.first);
        y = gcd(y, z.first);
        solution[z.second[0]] = 1;
        solution[z.second[1]] = 2;
        cntm2.push_back(z.first);
      }
    for (int z : cntm2) pos.erase(pos.find(z));
    cntm2.clear();
    DP_prev.clear();
    DP_prev[make_pair(x, y)] = make_tuple(-1, -1, -1, -1);
    DP_cur = DP_prev;
    for (const pair<int, vector<int>>& z : pos) {
      int v = z.first;
      int eidx = z.second[0];
      for (const auto& zz : DP_prev) {
        {
          clock_t t2 = clock();
          clock_t t = t2 - t1;
          double tx = (double)t / CLOCKS_PER_SEC;
          if (tx >= 0.4) {
            cout << "NO\n";
            return 0;
          }
        }
        int xx = zz.first.first, yy = zz.first.second;
        if (gcd(xx, v) != xx) {
          if (DP_cur.count(make_pair(gcd(xx, v), yy))) continue;
          DP_cur[make_pair(gcd(xx, v), yy)] = make_tuple(eidx, 1, xx, yy);
        }
        if (gcd(yy, v) != yy) {
          if (DP_cur.count(make_pair(xx, gcd(yy, v)))) continue;
          DP_cur[make_pair(xx, gcd(yy, v))] = make_tuple(eidx, 2, xx, yy);
        }
      }
      {
        clock_t t2 = clock();
        clock_t t = t2 - t1;
        double tx = (double)t / CLOCKS_PER_SEC;
        if (tx >= 0.4) {
          cout << "NO\n";
          return 0;
        }
      }
      DP_prev = DP_cur;
      Print();
    }
    Print();
  }
  cout << "NO\n";
  return 0;
}
