// https://szkopul.edu.pl/problemset/problem/TJVrS_hRC8W5Q6ZBW6mETAIm/site/?key=statement

#include <bits/stdc++.h>

// using namespace std;

// #define GARY_DBG
#define GARY_LIB

// #define int long long

constexpr int sizik = 100 * 1001, NIL = INT32_MAX, NIL2 = INT32_MIN;
constexpr int sizik2 = sizik * 3;

#define ar std::array
#define pr std::pair

int n;
int a[sizik];
int arrived[sizik];
int l[sizik];

void calc_l() {
    int next = 1;
    for (int i = 1; i <= n; i++) {
        arrived[a[i]] = i;
        while (next <= n && arrived[next] != 0) {
            l[arrived[next]] = i;
            next++;
        }
    }
}

// helper
bool is_nil(int x) {
    return (x == NIL || x == NIL2);
}

// helper
int max_1(int i, int j) {
    if (is_nil(i)) return j;
    if (is_nil(j)) return i;
    if (a[i] > a[j]) return i;
    return j;
}

// helper
int min_1(int i, int j) {
    if (is_nil(i)) return j;
    if (is_nil(j)) return i;
    if (a[i] < a[j]) return i;
    return j;
}

int k[sizik];
// int nn;

// "w przód"
namespace drzewo_turniejowe {

int d[sizik2];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        // important! -> we store index num!
        d[v] = tl;
        if (tl > n) d[v] = NIL2;
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        d[v] = max_1(d[2 * v], d[2 * v + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r) {
    if (l > r) return NIL2;
    if (tl == l && tr == r) return d[v];
    int tm = (tl + tr) / 2;
    return max_1(get(2 * v, tl, tm, l, std::min(tm, r)), get(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r));
}

void update(int v, int tl, int tr, int i) {
    if (tl == tr) {
        d[v] = NIL2;
    } else {
        int tm = (tl + tr) / 2;
        if (i <= tm) {
            update(2 * v, tl, tm, i);
        } else {
            update(2 * v + 1, tm + 1, tr, i);
        }
        d[v] = max_1(d[2 * v], d[2 * v + 1]);
    }
}

}

// "w tył"
namespace drzewo_z_nasluchiwaczami {

// używamy vector zamiast deque, ale odwracamy kolejność po build() — wtedy można pop_back()
std::vector<int> d[sizik2];
std::bitset<sizik> visited;

void build_helper_add(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        d[v].push_back(x);
        return;
    }
    int tm = (tl + tr) / 2;
    build_helper_add(2 * v, tl, tm, l, std::min(r, tm), x);
    build_helper_add(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, x);
}

void build() {
    // wyczyść/zeruj wektory przed budową (przydatne, jeśli build wywoływane wielokrotnie)
    for (int i = 0; i < sizik2; ++i) {
        d[i].clear();
    }

    std::vector<int> c;
    c.reserve(n);
    for (int i = 1; i <= n; i++) {
        c.push_back(i);
    }
    std::sort(c.begin(), c.end(), [](int i, int j) { return a[i] < a[j]; });

    for (const auto& id : c) {
        build_helper_add(1, 1, n, id + 1, l[id], id);
    }

    // ODWRÓĆ każdy wektor: dzięki temu najstarszy element będzie na back() i można używać pop_back()
    for (int i = 0; i < sizik2; ++i) {
        if (!d[i].empty()) {
            std::reverse(d[i].begin(), d[i].end());
        }
    }
}

void update(int x) {
    visited[x] = true;
}

// zwraca pierwszy nie-odwiedzony element w d[v] lub NIL
int get_mini_vec(int v) {
    auto& vec = d[v];
    // Usuń z końca wszystkie odwiedzone (pop_back jest amortyzowane i szybkie)
    while (!vec.empty() && visited[vec.back()]) {
        vec.pop_back();
    }
    if (vec.empty()) return NIL;
    return vec.back();
}

int get(int v, int tl, int tr, int x) {
    int curr = get_mini_vec(v);

    if (tl == tr) return curr;

    int tm = (tl + tr) / 2;
    if (x <= tm) {
        return min_1(curr, get(2 * v, tl, tm, x));
    } else {
        return min_1(curr, get(2 * v + 1, tm + 1, tr, x));
    }
}

} // namespace drzewo_z_nasluchiwaczami

std::bitset<sizik> is_deleted;

void Delete(int i) {
    is_deleted[i] = true;
    // drzewo_turniejowe::update(1, 1, nn, i);
    drzewo_turniejowe::update(1, 1, n, i);
    drzewo_z_nasluchiwaczami::update(i);
}

int get_edge(int i) {
    int x = drzewo_turniejowe::get(1, 1, n, i + 1, l[i]);
    if (!is_nil(x) && a[x] > a[i]) return x;
    x = drzewo_z_nasluchiwaczami::get(1, 1, n, i);
    if (!is_nil(x) && a[x] < a[i]) return x;
    return NIL;
}

void mod_dfs(int i, int color) {
    k[i] = color;
    Delete(i);
    while (true) {
        int j = get_edge(i);
        if (is_nil(j)) break;
        mod_dfs(j, 3 - color);
    }
}

bool check_if_good() {
    std::vector<std::stack<int>> s{{}, {}};
    s[0].push(NIL);
    s[1].push(NIL);
    int next = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] > s[k[i] - 1].top()) return false;
        s[k[i] - 1].push(a[i]);
        while ((s[0].top() == next) || (s[1].top() == next)) {
            if (s[0].top() == next)
                s[0].pop();
            else
                s[1].pop();
            next++;
        }
    }
    return true;
}

void solve() {
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    // oblicz l
    calc_l();

    // zbuduj strukturki
    // drzewo_turniejowe::build(1, 1, nn);
    drzewo_turniejowe::build(1, 1, n);
    drzewo_z_nasluchiwaczami::build();

    for (int i = 1; i <= n; i++) {
        if (!is_deleted[i]) {
            mod_dfs(i, 1);
        }
    }

    // check if good
    if (!check_if_good()) {
        std::cout << "NIE\n";
        return;
    }

    std::cout << "TAK\n";
    for (int i = 1; i <= n; i++) {
        std::cout << k[i] << " ";
    }
    std::cout << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}