#include "library3.h"
#include <bits/stdc++.h> 
#include <cassert>
#include <vector>

using namespace std;

#define pb push_back
#define sz(x) (int)(x).size()

mt19937 rnd(time(NULL));
template<typename T>
void shuf(vector<T>&x) {
    for (int i = 1; i < x.size(); i++) {
        swap(x[i], x[rnd() % i]);
    }
}

void solve(int N) {
    int n = N;
    vector<int> Q(n);
    for (int i = 0; i < n; i++) Q[i] = i;

    int la, req = 0;
    while (true) {
        shuf(Q);
        la = query(Q);
        req++;
        if (la == 0) {
            answer(Q); return;
        }
        if (la >= n - 2) break;
    }
    //cout << req << endl;
    vector<vector<int>> loops = {{0}};
    if (la == n - 1) {
        for (int i = 1; i < n; i++) loops.back().pb(i);   
    } else {
        loops.pb({});
        for (int i = 1; i < n; i++) {
            swap(Q[0], Q[i]);
            int na = query(Q);
            if (na == 0) {
                answer(Q);
                return;
            }
            swap(Q[0], Q[i]);
            if (na < la) {
                loops[0].pb(i);
            } else loops[1].pb(i);
        }
    }
    // for (int u : Q) cout << u << ' ';
    // cout << endl;
    while (true) {
        // cout << "iter\n";
        // for (auto u : loops) {
        //     for (int v : u) cout << v << ' ';
        //     cout << endl;
        // }
        int sw = 0;
        bool need = false;
        int curind = -1;
        vector<pair<int, int>> pos(sz(loops));
        for (auto l : loops) {
            curind++;
            if (l.size() >= 2) {
                need = true;
                int ind1 = rnd() % sz(l);
                int ind2 = (ind1 + 1 + rnd() % (sz(l) - 1)) % sz(l);
                swap(Q[l[ind1]], Q[l[ind2]]);
                pos[curind] = {ind1, ind2};
                sw++;
            }
        }
        if (!need) break;

        int curans = la - sw;
        //cout << "check " << curans << ' ' <<query(Q) << endl;
        vector<vector<int>> newloops;
        for (int i = 0; i < sz(loops); i++) {
            if (loops[i].size() == 1) {
                newloops.pb(loops[i]);
                continue;
            }
            for (int j = 0; j < 2; j++) newloops.pb({});
            newloops.back().pb(loops[i][pos[i].first]);
            newloops[sz(newloops) - 2].pb(loops[i][pos[i].second]);
            for (int j = 0; j < loops[i].size(); j++) {
                if (j == pos[i].first || j == pos[i].second) continue;
                // if (j == loops[i].size() - 1 && newloops[sz(newloops) - 2].empty()) {
                //     newloops[sz(newloops) - 2].pb(loops[i][j]);
                //     continue;
                // }
                // if (loops[i].size() == 2) {
                //     newloops[sz(newloops) - 2].pb(loops[i][j]);
                //     continue;
                // }
                swap(Q[loops[i][j]], Q[loops[i][pos[i].first]]);
                int rs = query(Q);
                if (rs == 0) {
                    answer(Q);
                    return;
                }
                if (rs < curans) {
                    newloops.back().pb(loops[i][j]);
                } else {
                    newloops[sz(newloops) - 2].pb(loops[i][j]);
                }
                swap(Q[loops[i][j]], Q[loops[i][pos[i].first]]);
            }
        }
        swap(loops, newloops);
        la = curans;
    }
    answer(Q);
}