#include <bits/stdc++.h>

#include "permutation.h"

std::mt19937 rnd;

void solve(int n) {
    std::vector<std::vector<int>> all;
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 1);
    do {
        all.push_back(p);
    } while (std::next_permutation(p.begin(), p.end()));

    bool start = true;
    while (all.size() > 1) {
        std::pair<double, std::vector<int>> min(1e9, p);
        if (!start) {
            for (int iter = 0; iter < 20; iter++) {
                std::shuffle(p.begin(), p.end(), rnd);
                if (iter < 10) {
                    // p = all[iter % all.size()];
                    for (int i = 0; i < n; i++) {
                        p[all[iter % all.size()][i] - 1] = i + 1;
                    }
                }
                std::vector<int> cum(n * n);

                for (int i = 0; i < all.size(); i++) {
                    int sum = 0;
                    for (int j = 0; j < n - 1; j++) {
                        sum += abs(all[i][p[j] - 1] - all[i][p[j + 1] - 1]);
                    }
                    cum[sum]++;
                }

                double cost = 0;
                int cnt = 0;
                for (int i = 0; i < n * n; i++) {
                    if (cum[i] > 0) {
                        cost += cum[i] * log2(cum[i]);
                        cnt++;
                    }
                }
                min = std::min(min, {cost, p});
            }
        } else {
            start = false;
        }
        int sum0 = query(p);

        bool suc = false;
        for (int i = 0; i < all.size(); i++) {
            int sum = 0;
            for (int j = 0; j < n - 1; j++) {
                sum += abs(all[i][p[j] - 1] - all[i][p[j + 1] - 1]);
            }
            if (sum != sum0) {
                suc = true;
                all[i] = {};
            }
        }
        if (!suc) {
            break;
        }
        all.erase(std::remove(all.begin(), all.end(), std::vector<int>()), all.end());
    }
    assert(all.size() >= 1);
    answer(all.front());
};