#include "bits/stdc++.h"
#define rep(i,a,n) for(auto i=a;i<=n;i++)
#define per(i,a,n) for(auto i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define all(A) A.begin(),A.end()
#define sz(A) (int)A.size()
template<class T> inline bool chmax(T &a, T b) { if(a < b) {a = b; return 1;} return 0; }
template<class T> inline bool chmin(T &a, T b) { if(b < a) {a = b; return 1;} return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v) 
{
    bool first = 1;
    string res = "{";
    for(const auto &x: v) 
    {
        if (!first) res += ", ";
        first = 0;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.FI) + ", " + to_string(p.SE) + ")"; }

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) 
{
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifndef ONLINE_JUDGE
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) if(0) puts("No effect.")
#endif

using ll = long long;
// using LL = __int128;
using pii = pair<int,int>;
using vi = vector<int>;
using db = double;
using ldb = long double;

const int maxn = 2'000'000;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

template<class T, T INF, int maxn> struct BIT
{
    int n;
    T a[maxn + 5];
    int id[maxn + 5];
    void init(int _n)
    {
        n = _n;
        rep(i, 1, n) a[i] = -INF;
    }
    void add(int i, T x, int y) { for(; i <= n; i += i & -i) if(chmax(a[i], x)) id[i] = y; }
    pair<T, int> ask(int i)
    {
        T ans = -INF;
        int ID = -1;
        for(; i; i -= i & -i) if(chmax(ans, a[i])) ID = id[i];
        return mp(ans, ID);
    }
};

int main()
{
    static int pw[25];
    pw[0] = 1;
    rep(i, 1, 15) pw[i] = pw[i - 1] * 3;

    int n; scanf("%d", &n);
    vi a(n);
    for(auto &x: a) scanf("%d", &x);
    vi L = vi(a.begin(), a.begin() + n / 2);
    vi R = vi(a.begin() + n / 2, a.end());
    vector<pair<pii, int>> A, B;
    function<void(vector<pair<pii, int>>&, vi&, int, int, int, int, int)> dfs = [&](vector<pair<pii, int>> &res, vi &vec, int dep, int A, int D, int B, int msk)
    {
        if(dep == sz(vec))
        {
            res.pb(mp(pii{A - D, D - B}, msk));
            return;
        }
        dfs(res, vec, dep + 1, A + vec[dep], D, B, msk);
        dfs(res, vec, dep + 1, A, D + vec[dep], B, msk + pw[dep]);
        dfs(res, vec, dep + 1, A, D, B + vec[dep], msk + pw[dep] * 2);
    };
    dfs(A, L, 0, 0, 0, 0, 0);
    dfs(B, R, 0, 0, 0, 0, 0);
    for(auto &[it, msk]: B) it = {-it.FI, -it.SE};
    sort(all(A));
    sort(all(B)); reverse(all(B));
    vi vec;
    for(auto [it, msk]: B) vec.pb(it.SE);
    sort(all(vec)); vec.erase(unique(all(vec)), vec.end());
    int N = sz(vec);
    auto getid = [&](int x) { return lower_bound(all(vec), x) - vec.begin() + 1; };
    static BIT<int, inf, maxn> bit;
    bit.init(N);
    assert(N <= maxn);
    int best = inf;
    pii ansmsk = {-1, -1};
    for(auto [it, msk]: A)
    {
        auto [x1, y1] = it;
        while(sz(B) && B.back().FI.FI <= x1)
        {
            auto [x2, y2] = B.back().FI;
            int msk = B.back().SE;
            B.pop_back();
            int pos = getid(y2);
            bit.add(pos, x2 + y2, msk);
        }
        auto pos = getid(y1 + 1) - 1;
        auto [mx, msk2] = bit.ask(pos);
        if(chmin(best, x1 + y1 - mx)) ansmsk = {msk, msk2};
    }
    vi ans;
    auto [X, Y] = ansmsk;
    rep(i, 1, n / 2) ans.pb(X % 3), X /= 3;
    rep(i, 1, n - n / 2) ans.pb(Y % 3), Y /= 3;
    rep(i, 0, n - 1) printf("%d%c", ans[i] + 1, " \n"[i == n - 1]);
    return 0;
}