#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;
    };
    int near = -1;
    vector<int> lft, rgt, other;
    while (near == -1) {
        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;
        }
        if (min(lft.size(), rgt.size()) <= 3) {
            if (lft.size() > rgt.size()) lft = rgt;
            std::shuffle(lft.begin(), lft.end(), gen);
            for (auto& v : lft) if (calc(v) == 1) {
                near = v;
                break;
            }
            break;
        }
        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;
        }
        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);
            }
        }
        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;
    }
    assert(near != -1);
    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>> gr = {right};
    std::shuffle(left.begin(), left.end(), gen);
    vector<int> ord(n);
    for (auto& v : left) {
        int cnt = 1;
        int vl = -1, vr = int(gr.size());
        while (vl + 1 < vr) {
            int vm = (vl + vr) / 2;
            if (ask(v, gr[vm][0]) != 1) {
                vr = vm;
            } else {
                vl = vm;
            }
        }
        for (int i = 0; i < vl; i++) cnt += gr[i].size();
        int l = max(0, vl), r = min(int(gr.size()), vr + 1);
        while (l < r) {
            int m = (l + r) / 2;
            auto ids = gr[m];
            int c = 0;
            for (auto& u : ids) c += (ask(v, u) == 1);
//            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);
    }
    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);
            assert(l + 1 == r);
            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]);
    }
    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;
}