#include "checkpoint.h"
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

void get_order(int l, int r, vector<int>& v) {
    if (l < r) {
        const int m = (l + r) / 2;

        v.push_back(m);
        get_order(l, m-1, v);
        get_order(m+1, r, v);
    }
}

vector<int> get_order(int n) {
    vector<int> res;
    get_order(0, n, res);
    return res;
}

vector<int> guess(int n) {
    if (n == 3) {
        return vector<int>{1, 2, 3};
    }
    
    mt19937 rng(1337228);
    vector<int> side(n+1), is_corner(n+1);
    vector<int> unknown(n-1);
    for (int i = 0; i < n-1; ++i) unknown[i] = i+2;
    shuffle(unknown.begin(), unknown.end(), rng);

    vector<int> corners, lhs_strong, rhs_strong;
    vector<vector<int>> dom(n+1);
    vector<int> pos(n+1, -1);

    const int RHS_SIDE = +1;
    const int LHS_SIDE = -1;

    vector<int> q(n);
    q[n/2] = 1;

    while (!unknown.empty()) {
        const int x = unknown.back();
        if (side[x] != 0 || is_corner[x]) {
            unknown.pop_back();
            continue;
        } 

        int updated_side = LHS_SIDE;
        if (lhs_strong.empty() && rhs_strong.empty()) {
            for (int i = 2; i <= n; ++i)
                if (i != x && min_value(i, x) == 1)
                    dom[x].push_back(i);

            if (dom[x].empty()) {
                is_corner[x] = 1;
                continue;
            } else {
                side[x] = RHS_SIDE;
                for (int y : dom[x]) side[y] = LHS_SIDE;
                lhs_strong = dom[x];
                updated_side = LHS_SIDE;
            }
        } else {
            assert(!rhs_strong.empty());

            auto check = [&](int c_side) -> bool {
                vector<int>& v = c_side == LHS_SIDE ? lhs_strong : rhs_strong;
                const int another_side = -c_side;

                for (int y : v) {
                    if (min_value(y, x) == 1) dom[x].push_back(y);
                }
                
                if (dom[x].empty()) {
                    return false;
                } else {
                    side[x] = another_side;
                    updated_side = c_side;
                    v = dom[x];
                    return true;
                }
            };

            if (lhs_strong.size() < rhs_strong.size()) {
                if (!check(LHS_SIDE) && !check(RHS_SIDE)) {
                    is_corner[x] = 1;
                    continue;
                }
            } else {
                if (!check(RHS_SIDE) && !check(LHS_SIDE)) {
                    is_corner[x] = 1;
                    continue;
                }
            }
        }

        if (updated_side == LHS_SIDE) {
            q[n - (int)dom[x].size() - 1] = x;
        } else {
            q[dom[x].size()] = x;
        }

        const int another_side = -updated_side;
        vector<int>& v = updated_side == LHS_SIDE ? lhs_strong : rhs_strong;
        const int y = v[rng() % v.size()];

        if (!dom[y].empty()) continue;

        for (int i = 1; i <= n; ++i) 
            if (side[i] == another_side) dom[y].push_back(i);

        for (int i = 0; i < (int)unknown.size(); ) {
            const int z = unknown[i];
            if (side[z] != 0 || is_corner[z]) {
                swap(unknown[i], unknown.back());
                unknown.pop_back();
                continue;
            }
            ++i;

            if (min_value(y, z) == 1) {
                side[z] = another_side;
                dom[y].push_back(z);
            }
        }

        if (updated_side == LHS_SIDE) {
            q[dom[y].size()] = y;
        } else {
            q[n - (int)dom[y].size() - 1] = y;
        }

        if (updated_side == LHS_SIDE && rhs_strong.empty()) rhs_strong = dom[y];
    }

    vector<vector<int>> blocks;
    vector<int> bL, bR;
    vector<int> block_id(n+1, -1);

    vector<int> ord(n, 0);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int lhs, int rhs) {
        return dom[lhs].size() < dom[rhs].size();
    });

    for (int i : ord) {
        if (dom[i].empty()) continue;
        
        int new_block = (int)blocks.size();
        blocks.emplace_back();

        for (int j : dom[i]) {
            if (block_id[j] != -1) continue;
            block_id[j] = new_block;
            blocks[new_block].push_back(j);
        }

        if (side[i] == LHS_SIDE) {
            bR.push_back(n/2 + dom[i].size() + 1);
            bL.push_back(bR.back() - blocks[new_block].size());
        } else {
            bL.push_back(n/2 - dom[i].size());
            bR.push_back(bL.back() + blocks[new_block].size());
        }
    }

    for (int i = 0; i < n; ++i) if (q[i] > 0) pos[q[i]] = i;

    vector<int> covering_block(n, -1);
    for (int i = 0; i < (int)blocks.size(); ++i) {
        for (int j = bL[i]; j < bR[i]; ++j) covering_block[j] = i;
    }

    auto shrink_block = [&](int bid) {
        auto& B = blocks[bid];
        for (int i = 0; i < (int)B.size(); ) {
            block_id[B[i]] = bid;
            if (pos[B[i]] != -1) {
                swap(B[i], B.back());
                block_id[B.back()] = -1;
                B.pop_back();
            } else {
                ++i;
            }
        }

        int& L = bL[bid];
        int& R = bR[bid];
        while (L < R && q[L+0] != 0) covering_block[L++] = -1;
        while (L < R && q[R-1] != 0) covering_block[--R] = -1;

        if (L + 1 == R) {
            assert(B.size() == 1);
            const int x = B.back();
            B.clear();
            block_id[x] = -1;
            pos[x] = L;
            q[L] = x;
            covering_block[L] = -1;
            ++L;
        }
    };

    for (int i = 0; i < (int)blocks.size(); ++i) shrink_block(i);

    shuffle(ord.begin(), ord.end(), rng);
    for (int x : ord) {
        if (x == 1 || is_corner[x] || pos[x] != -1) continue;
        assert(block_id[x] != -1);
        const int bid = block_id[x];

        const int L = bL[bid], R = bR[bid];
        const int cL = side[x] == LHS_SIDE ? L + n/2 + 1 : L - n/2;
        const int cR = side[x] == LHS_SIDE ? R + n/2     : R - n/2 - 1;

        vector<pi> to_ask;

        int dom_sz = side[x] == LHS_SIDE ? L : n - R;

        vector<int> beauty;
        for (int i = cL; i != cR; ++i) {
            if (q[i] != 0) beauty.push_back(q[i]);
        }
        if (side[x] == RHS_SIDE) reverse(beauty.begin(), beauty.end());

        /* bin search */ {
            // экономит < 100 запросов (очень незначимо)
            int L = -1, R = (int)beauty.size();
            while (L + 1 != R) {
                int M = (L + R) / 2;
                if (min_value(beauty[M], x) == 1) L = M;
                else R = M;
            }
            dom_sz += R;
        }

        /* another bin search */ {
            beauty.clear();
            for (int i = cL; i < cR; ) {
                if (covering_block[i] != -1) {
                    const int cbi = covering_block[i];
                    i = bR[cbi];
                    beauty.push_back(cbi);

                    if (side[x] == RHS_SIDE) {
                        for (int i = cR; i < bR[cbi]; ++i)
                            if (q[i] == 0) --dom_sz;
                    } else {
                        for (int i = bL[cbi]; i < cL; ++i)
                            if (q[i] == 0) --dom_sz;
                    }
                } else {
                    ++i;
                }
            }
            if (side[x] == RHS_SIDE) reverse(beauty.begin(), beauty.end());

            vector<int> to_check;
            if (beauty.size() <= 2) {
                to_check = beauty;
            } else {
                // L -- min_value(x, random) == 1, R : == 0
                int L = -1, R = beauty.size();
                while (L + 1 != R) {
                    int M = (L + R) / 2;
                    const int cbi = beauty[M];
                    if (min_value(blocks[cbi].back(), x) == 1) {
                        L = M;
                    } else {
                        R = M;
                    }
                }

                if (L >= 0) to_check.push_back(beauty[L]);
                if (R < (int)beauty.size()) to_check.push_back(beauty[R]);
                for (int i = 0; i < L; ++i) dom_sz += (int)blocks[beauty[i]].size();
            }

            for (int cbi : to_check) {
                vector<int> U, V;
                for (int y : blocks[cbi]) {
                    if (min_value(y, x) == 1) {
                        U.push_back(y);
                        ++dom_sz;
                    } else {
                        V.push_back(y);
                    }
                }

                const int nxt_i = bR[cbi];

                if (!V.empty() && !U.empty()) {
                    if (side[x] == RHS_SIDE) swap(U, V);

                    int M = bL[cbi], cnt = 0;
                    while (cnt < (int)U.size()) {
                        if (q[M] == 0) ++cnt;
                        ++M;
                    }

                    blocks.push_back(V);
                    bL.push_back(M);
                    bR.push_back(bR[cbi]);
                    for (int j = bL.back(); j != bR.back(); ++j)
                        covering_block[j] = (int)blocks.size()-1;

                    bR[cbi] = M;
                    blocks[cbi] = U;

                    shrink_block(cbi);
                    shrink_block((int)blocks.size()-1);
                }
            }
        }

        const int p = side[x] == LHS_SIDE ? dom_sz : n - dom_sz - 1;
        
        int was = q[p];
        pos[x] = p;
        q[p] = x;
        shrink_block(bid);

        assert(was == 0);
    }

    for (int x = 1; x <= n; ++x) if (is_corner[x]) corners.push_back(x);
    assert(corners.size() == 2);
    const int ca = *min_element(corners.begin(), corners.end());
    const int cb = *max_element(corners.begin(), corners.end());

    q[0] = ca;
    q[n-1] = cb;

    if (q[1] > ca) {
        if (min_value(cb, q[1]) != ca)
            swap(q[0], q[n-1]);
    } else if (q[n-2] > ca) {
        if (min_value(cb, q[n-2]) == ca)
            swap(q[0], q[n-1]);
    }

    return q;
}
