#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

#include "permutation.h"

std::mt19937 rnd;
int n;

int cum(const std::vector<int>& a, const std::vector<int>& p) {
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += abs(a[p[i] - 1] - a[p[i + 1] - 1]);
    }
    return sum;
}

void solve(int n) {
    while (true) {
        assert(clock() * 1.0 / CLOCKS_PER_SEC < 0.6);
    }

    return;

    ::n = n;
    std::vector<std::vector<int>> all;
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 1);
    std::shuffle(p.begin(), p.end(), rnd);
    {
        int sum0 = query(p);
        std::vector<int> q(n);
        std::iota(q.begin(), q.end(), 1);
        do {
            if (cum(q, p) == sum0) {
                all.push_back(q);
            }
            assert(clock() * 1.0 / CLOCKS_PER_SEC < 0.6);
        } while (std::next_permutation(q.begin(), q.end()));
    }

    bool start = true;
    int cnt = 0;
    while (all.size() > 1) {
        cnt++;
        assert(cnt <= 7);

        std::pair<double, std::vector<int>> min(1e9, p);
        for (int iter = 0; iter < 10; iter++) {
            std::shuffle(p.begin(), p.end(), rnd);
            if (iter < 3) {
                // 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++) {
                cum[::cum(all[i], p)]++;
                assert(clock() * 1.0 / CLOCKS_PER_SEC < 0.6);
            }

            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});
        }

        int sum0 = query(p);

        bool suc = false;
        for (int i = 0; i < all.size(); i++) {
            assert(clock() * 1.0 / CLOCKS_PER_SEC < 0.6);

            if (::cum(all[i], p) != 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());
};