// #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 shuffle(auto& vec) {
    std::shuffle(vec.begin(), vec.end(), rnd);
    // for (int i = 0; i < vec.size(); i++) {
    //     std::swap(vec[i], vec[rnd() % (i + 1)]);
    // }
}

void solve(int n) {
    ::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);
    shuffle(p);

    {
        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);
            }
        } while (std::next_permutation(q.begin(), q.end()));
    }

    bool start = true;
    while (all.size() > 1) {
        std::pair<double, std::vector<int>> min(1e9, p);
        for (int iter = 0; iter < 100; iter++) {
            // std::shuffle(p.begin(), p.end(), rnd);
            shuffle(p);

            if (iter < 5) {
                // 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)]++;
            }

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

        p = min.second;
        int sum0 = query(p);

        bool suc = false;
        for (int i = 0; i < all.size(); i++) {
            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());
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<std::vector<int>, std::allocator<std::vector<int> > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::vector<int>]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~