#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

void Solve(int N) {
    vector<int> bal(2 * N + 1);
    auto isIn = [&](int x) {
        return bal[x];
    };
    int Q = 0;
    auto query = [&](int f) -> pair<int, int> {
        Q += 1;
        int r = Query(f);
        return {r, bal[f] ^= 1};
    };
    vector<int> L, R;
    vector<int> ord(2 * N);
    iota(ord.begin(), ord.end(), 1);
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(ord.begin(), ord.end(), rnd);
    for (int i : ord) {
        if (L.size() == N) {
            R.push_back(i);
            continue;
        }
        int x = query(i).first;
        if (x == size(L) + 1) {
            L.push_back(i);
        } else {
            R.push_back(i);
        }
    }
//    swap(L, R);

    int qIn = L.size();
    int c = 0, f = 0;
    auto dfs = [&](auto self, vector<int> a, vector<int> b) {
        if (a.size() == 1) {
            Answer(a[0], b[0]);
            return;
        }
        int iQ = Q;
        vector<int> in, out, inb, outb;
        for (int x : a) {
            (isIn(x) ? in : out).push_back(x);
        }
        for (int x : b) {
            (isIn(x) ? inb : outb).push_back(x);
        }
        if (a.size() == 2 && inb.size() == 1) {
            swap(inb, in);
            swap(outb, out);
            swap(a, b);
        }
        if (a.size() == 2) {
            if (in.size() == 0) {
                in.push_back(out.back());
                out.pop_back();
                qIn = query(in[0]).first;
            } else if (in.size() == 2) {
                out.push_back(in.back());
                in.pop_back();
                qIn = query(out[0]).first;
            }
            if (in.size() == 1) {
                auto [res, t] = query(b[0]);
                if (res == qIn) {
                    Answer(in[0], b[0]);
                    Answer(out[0], b[1]);
                } else {
                    Answer(in[0], b[1]);
                    Answer(out[0], b[0]);
                }
                qIn = res;
                return;
            } else {
                assert(false);
            }
        }
        int needIn = in.size() > out.size() ? (a.size() + 1) / 2 : a.size() / 2;
        while (in.size() > needIn) {
            qIn = query(in.back()).first;
            out.push_back(in.back());
            in.pop_back();
        }
        while (in.size() < needIn) {
            qIn = query(out.back()).first;
            in.push_back(out.back());
            out.pop_back();
        }
        shuffle(b.begin(), b.end(), rnd);
        vector<int> lb, rb;
        for (int x : b) {
            if (rb.size() == in.size()) {
                lb.push_back(x);
                continue;
            } else if (lb.size() == out.size()) {
                rb.push_back(x);
                continue;
            }
            auto [res, t] = query(x);
            if (res == qIn) {
                rb.push_back(x);
            } else {
                qIn = res;
                lb.push_back(x);
            }
        }
        self(self, in, rb);
        self(self, lb, out);
        if (a.size() == 3) {
            c += Q - iQ;
            f += 1;
        }
    };
    dfs(dfs, L, R);
    cerr << double(c) / f << " " << f << endl;
}