#include "checkpoint.h"
#include "bits/stdc++.h"

using namespace std;

//mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
mt19937 gen(22);

map<pair<int, int>, int> mem;
int ask(int i, int j) {
    if (i > j) swap(i, j);
    if (i == j) return i;
    if (mem.find({i, j}) == mem.end()) {
        mem[{i, j}] = min_value(i, j);
    }
    return mem[{i, j}];
}

std::vector<int> guess(int n) {
    mem.clear();
    if (n == 1) {
        return {1};
    }
    if (n == 3) {
        return {1, 2, 3};
    }
    auto calc = [&] (int x) {
        int cnt = 0;
        for (int y = 2; y <= n; y++) {
            if (x != y) {
                cnt += (ask(x, y) == 1);
            }
        }
        return n / 2 - cnt;
    };
//    vector<vector<int>> blocks(n + 1);
//    for (int x = 2; x < n; x++) {
//        blocks[ask(x, n)].push_back(x);
//    }
//    int mx = n;
//    while (blocks[mx].empty()) mx--;
    int near = -1;
    vector<int> lft, rgt, other;
//    debug(n);
//    auto print = [&] (vector<int> nodes) {
//        debug(nodes.size());
//        vector<int> kek;
//        for (auto& v : nodes) kek.push_back(calc(v));
//        std::sort(kek.begin(), kek.end());
//        int i = 0;
//        while (i < kek.size()) {
//            int l = kek[i], tmp = l;
//            while (i < kek.size() && kek[i] - tmp <= 1) {
//                tmp = kek[i++];
//            }
//            debug(l, tmp);
//        }
//    };
    while (near == -1) {
//        debug(lft, rgt, other);
//        debug(mem.size());
//        print(lft);
//        print(rgt);
//        print(other);
        if (lft.empty()) {
            while (1) {
                int v = gen() % (n - 1) + 2;
                for (int i = 2; i <= n; i++) {
                    if (ask(v, i) == 1) lft.push_back(i);
                }
//                debug(v, lft);
                if (lft.size() == n / 2 - 1) {
                    near = v;
                    break;
                }
                if (lft.size() >= 1 && lft.size() < n / 2 - 2) {
                    break;
                }
                lft.clear();
            }
            continue;
        }
        if (lft.size() == 1) {
            near = lft[0];
            continue;
        }
        if (rgt.empty()) {
            while (1) {
                int v = lft[gen() % lft.size()];
//                debug(v);
                for (int i = 2; i <= n; i++) {
                    if (ask(v, i) == 1) rgt.push_back(i);
                }
                if (rgt.size() == n / 2 - 1) {
                    near = v;
                    break;
                }
                if (rgt.size() >= 1 && rgt.size() < n / 2 - 2) {
                    break;
                }
                rgt.clear();
            }
            continue;
        }
        if (rgt.size() == 1) {
            near = rgt[0];
            continue;
        }
        if (other.empty()) {
            set<int> usd;
            for (auto& v : lft) usd.insert(v);
            for (auto& v : rgt) usd.insert(v);
            for (int i = 2; i <= n; i++) {
                if (usd.find(i) == usd.end()) {
                    other.push_back(i);
                }
            }
            continue;
        }
        int v = lft[gen() % lft.size()];
        vector<int> lother, rother;
        {
            for (auto &u: other) {
                if (ask(v, u) == 1) {
                    lother.push_back(u);
                } else {
                    rother.push_back(u);
                }
            }
            if (rother.size() <= 2) {
                if (calc(v) == 1) {
                    near = v;
                } else {
                    for (auto &z: rother) {
                        if (calc(z) == n / 2 - 1) {
                            for (int y = 2; y <= n; y++) {
                                if (ask(z, y) == 1) {
                                    near = y;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                }
                continue;
            }
            other = rother;
        }
        {
            v = rgt[gen() % rgt.size()];
            lother.clear();
            rother.clear();
            for (auto &u: other) {
                if (ask(v, u) == 1) {
                    lother.push_back(u);
                } else {
                    rother.push_back(u);
                }
            }
            if (rother.size() <= 2) {
                if (calc(v) == 1) {
                    near = v;
                } else {
                    for (auto &z: rother) {
                        if (calc(z) == n / 2 - 1) {
                            for (int y = 2; y <= n; y++) {
                                if (ask(z, y) == 1) {
                                    near = y;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                }
                continue;
            }
//            debug(other.size(), rother.size());
        }
        other = rother;
        v = other[gen() % other.size()];
        vector<int> lft1, lft2, rgt1, rgt2;
        for (auto& u : lft) {
            if (ask(v, u) == 1) {
                lft1.push_back(u);
            } else {
                lft2.push_back(u);
            }
        }
        for (auto& u : rgt) {
            if (ask(v, u) == 1) {
                rgt1.push_back(u);
            } else {
                rgt2.push_back(u);
            }
        }
//        debug(calc(v), lft1.size(), rgt1.size(), lft2.size(), rgt2.size());
        if (lft1.empty() && rgt1.empty()) {
            other.erase(std::find(other.begin(), other.end(), v));
            continue;
        }
        if (lft1.empty()) {
            rgt = rgt1;
            continue;
        }
        if (rgt1.empty()) {
            lft = lft1;
            continue;
        }
        lft = lft1, rgt = rgt1;
    }
//    debug(near);
//    vector<int> res;
//    if (blocks[1].empty()) {
//        for (int y = 2; y < n; y++) {
//            if (ask(y, mx) == 1) {
//                near = y;
//                break;
//            }
//        }
//
//    } else {
////        for (int y = 2; y < n; y++) {
////            if (ask(n, y) != 1 && ask(y, mx) == 1) {
////                for (int z = 2; z < n; z++) {
////                    if (!blocks[z].empty()) {
////                        if (ask(z, y) == 1) {
////
////                            break;
////                        }
////                    }
////                }
////                break;
////            }
////        }
//    }
//    while (near == -1) {
//        int x = gen() % (n - 1) + 2;
//        if (res.empty()) {
//            for (int i = 2; i <= n; i++) {
//                if (ask(x, i) == 1) {
//                    res.push_back(i);
//                }
//            }
//        } else {
//            std::shuffle(res.begin(), res.end(), gen);
//            if (ask(x, res[0]) == 1) {
//                vector<int> nres;
//                for (auto& y : res) {
//                    if (ask(x, y) == 1) {
//                        nres.push_back(y);
//                    }
//                }
//                res = nres;
//            }
//        }
//        if (res.size() <= 10) {
//            for (auto& v : res) {
//                if (calc(v) == 1) {
//                    near = v;
//                    break;
//                }
//            }
//        }
//    }
//    if (blocks[1].empty()) {
//        for (int y = 2; y < n; y++) {
//            if (ask(y, mx) == 1) {
//                near = y;
//                break;
//            }
//        }
//        if (near == -1) {
//            int g = 1;
//            while (blocks[g].empty()) g++;
//            for (auto &x: blocks[g]) {
//                if (calc(x) == 1) {
//                    near = x;
//                    break;
//                }
//            }
//        }
//    } else {
//        int g = 1;
//        while (blocks[g].empty()) g++;
//        for (auto &x: blocks[g]) {
//            if (calc(x) == 1) {
//                near = x;
//                break;
//            }
//        }
//    }
//    cout << iters * n << endl;
    assert(near != -1);
//    debug(mem.size());
    vector<int> p(n);
    p[0] = 1;
    vector<vector<int>> dist(n + 1);
    dist[1].push_back(near);
    vector<int> left, right;
    for (int i = 2; i <= n; i++) {
        if (i != near) {
            if (ask(i, near) == 1) {
                left.push_back(i);
            } else {
                right.push_back(i);
            }
        }
    }
    vector<vector<int>> gl = {left};
    vector<vector<int>> gr = {right};
//    int iters = 0;
//    while (iters--) {
//        debug(gl.size(), gr.size());
//        bool upd = false;
//        for (int it = 0; it < 2; it++) {
//            swap(gl, gr);
//            swap(left, right);
//            int v = left[gen() % left.size()];
//            {
////                int v = gl[mx.second][gen() % gl[mx.second].size()];
//                upd = true;
//                int l = 0, r = int(gr.size());
//                while (l < r) {
//                    int m = (l + r) / 2;
//                    auto ids = gr[m];
//                    int c = 0;
//                    for (auto& u : ids) c += (ask(v, u) == 1);
//                    if (c == ids.size()) {
//                        l = m + 1;
//                    } else if (c == 0) {
//                        r = m;
//                    } else {
//                        vector<int> lft, rgt;
//                        for (auto& u : gr[m]) {
//                            if (ask(v, u) == 1) {
//                                lft.push_back(u);
//                            } else {
//                                rgt.push_back(u);
//                            }
//                        }
//                        assert(!lft.empty() && !rgt.empty());
//                        gr[m] = rgt;
//                        gr.insert(gr.begin() + m, lft);
//                        break;
//                    }
//                }
//            }
//        }
//        if (!upd) break;
//    }
    std::shuffle(left.begin(), left.end(), gen);
    vector<int> ord(n);
    vector<int> cnt(n + 1, 0);
    for (auto& v : left) cnt[v]++;
    auto rec = [&] (auto&& rec, vector<int> a, vector<int> b) -> void {
        if (a.empty() || b.empty()) return;
        if (min(a.size(), b.size()) <= 1) {
            for (auto& v : a) {
                for (auto& u: b) {
                    cnt[v] += (ask(v, u) == 1);
                    cnt[u] += (ask(v, u) == 1);
                }
            }
            return;
        }
        int v = a[gen() % a.size()];
        a.erase(find(a.begin(), a.end(), v));
        vector<int> lb, rb;
        for (auto& u : b) {
            if (ask(v, u) == 1) {
                cnt[v]++;
                cnt[u]++;
                lb.push_back(u);
            } else {
                rb.push_back(u);
            }
        }
        shuffle(lb.begin(), lb.end(), gen);
        shuffle(rb.begin(), rb.end(), gen);
        vector<int> la, ra;
        int add = 0;
        for (auto& v : a) {
            if (lb.empty()) {
                ra.push_back(v);
            } else if (rb.empty()) {
                la.push_back(v);
            } else {
                if (ask(v, lb[0]) == 1) {
                    ra.push_back(v);
                    if (ask(v, rb[0]) != 1) {
                        la.push_back(v);
                    } else {
                        add++;
                        cnt[v] += lb.size();
                    }
                } else {
                    la.push_back(v);
                }
            }
        }
        for (auto& v : lb) cnt[v] += add;
        rec(rec, lb, la);
        rec(rec, rb, ra);
    };
    rec(rec, left, right);
//    debug(left, right);
    for (auto& v : left) {
//        debug(v, n / 2 - cnt[v]);
        ord[n / 2 - cnt[v]] = v;
        dist[n / 2 - cnt[v]].push_back(v);
//        if (dist[n / 2 - cnt[v]].size() > 1) {
//            debug(n / 2 - cnt[v]);
//        }
    }
    for (auto& v : right) {
//        debug(v, n / 2 - cnt[v]);
        ord[n / 2 - cnt[v]] = v;
        dist[n / 2 - cnt[v]].push_back(v);
//        if (dist[n / 2 - cnt[v]].size() > 1) {
//            debug(n / 2 - cnt[v]);
//        }
    }
//    const int K = 50;
//    for (auto& v : left) {
//        int cnt = 1;
//        int l = 0, r = int(gr.size());
//        while (l < r) {
//            int m = (l + r) / 2;
//            auto ids = gr[m];
//            std::shuffle(ids.begin(), ids.end(), gen);
//            int c = 0;
//            for (int i = 0; i < int(ids.size()); i++) {
//                c += (ask(v, ids[i]) == 1);
//                if (c == 0 && i >= K) {
//                    break;
//                }
//                if (c == i + 1 && i >= K) {
//                    c = ids.size();
//                    break;
//                }
//            }
////            debug(v, m, c);
//            if (c == ids.size()) {
//                while (l <= m) {
//                    cnt += int(gr[l].size());
//                    l++;
//                }
//            } else if (c == 0) {
//                r = m;
//            } else {
////                debug(v, c);
//                while (l < m) {
//                    cnt += int(gr[l].size());
//                    l++;
//                }
//                cnt += c;
//                vector<int> lft, rgt;
//                for (auto& u : gr[m]) {
//                    if (ask(v, u) == 1) {
//                        lft.push_back(u);
//                    } else {
//                        rgt.push_back(u);
//                    }
//                }
//                assert(!lft.empty() && !rgt.empty());
//                gr[m] = rgt;
//                gr.insert(gr.begin() + m, lft);
//                break;
//            }
//        }
//        ord[n / 2 - cnt] = v;
//        dist[n / 2 - cnt].push_back(v);
//    }
//    debug(mem.size(), ord);
//    int pos = 2;
//    for (auto& group : gr) {
//        for (auto& v : group) {
//            int l = pos, r = min(n / 2 + 1, pos + (int) group.size());
//            l = min(l, r - 1);
////            debug(l, r, n / 2 - (r - 1) + 1, n / 2 - l + 1);
//            while (l + 1 < r) {
//                int m = (l + r) / 2;
//                if (ask(ord[n / 2 - m + 1], v) == 1) {
//                    r = m;
//                } else {
//                    l = m;
//                }
//            }
////            debug(l, v);
//            dist[l].push_back(v);
//        }
//        pos += group.size();
//    }
//    debug(near);
//    debug(dist, gr, left);
    if (dist[n / 2 + 1].size() == 1) {
        dist[n / 2].push_back(dist[n / 2 + 1][0]);
    }
//    debug(dist);
    int l = 1, r = n - 1;
    p[l++] = dist[1][0];
    p[r--] = dist[1][1];
    for (int i = 2; i < n / 2; i++) {
        if (ask(dist[i][0], p[1]) > 1) {
            p[l++] = dist[i][0];
            p[r--] = dist[i][1];
        } else {
            p[l++] = dist[i][1];
            p[r--] = dist[i][0];
        }
    }
    int x = dist[n / 2][0], y = dist[n / 2][1];
    if (x < y) swap(x, y);
    if (ask(p[l - 1], x) > y) {
        p[l] = x, p[r] = y;
    } else if (ask(p[r + 1], x) > y) {
        p[r] = x, p[l] = y;
    } else if (ask(p[l - 1], x) == y){
        p[r] = x, p[l] = y;
    } else if (ask(p[r + 1], x) == y) {
        p[l] = x, p[r] = y;
    } else {
        p[l] = x, p[r] = y;
    }
    return p;
}