#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "fun.h"
using namespace std;
#define ll long long
vector<int> ans;
set<int> rem;
int n;
void solve(int i) {
if (rem.find(i) == rem.end()) {
return;
}
if ((i << 1) > n) {
ans.push_back(i);
rem.erase(ans.back());
return;
}
rem.erase(i);
vector<int> v[2];
for (auto j : rem) {
if (j == i) continue;
int diff = __lg(j) - __lg(i << 1);
v[(j >> diff) != (i << 1)].push_back(j);
}
int cur = 0;
while (v[1].size()) {
ans.push_back(v[cur].back());
rem.erase(ans.back());
v[cur].pop_back();
cur ^= 1;
}
solve(i << 1);
ans.push_back(i);
}
bool check(const std::vector<int>& fun_tour) {
if (static_cast<int>(fun_tour.size()) != n) {
return 0;
}
std::vector<bool> visited_attractions(n, false);
for (int i = 0; i < n; ++i) {
if (fun_tour[i] < 0 || fun_tour[i] >= n) {
return 0;
}
if (visited_attractions[fun_tour[i]]) {
return 0;
}
visited_attractions[fun_tour[i]] = true;
}
int last_travel_time = hoursRequired(fun_tour[0], fun_tour[1]);
for (int i = 2; i < n; ++i) {
int travel_time = hoursRequired(fun_tour[i - 1], fun_tour[i]);
if (travel_time > last_travel_time) {
return 0;
}
last_travel_time = travel_time;
}
return 1;
}
vector<int> solve() {
int dist[n][n]{};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = hoursRequired(i, j);
}
}
int u = 0;
array<int, 2> mx = {-1, -1};
for (int i = 0; i < n; i++) {
mx = max(mx, {dist[u][i], i});
}
u = mx[1];
vector<int> ans, v;
for (int i = 0; i < n; i++) {
if (i == u) continue;
v.push_back(i);
}
ans.push_back(u);
while (v.size()) {
mx = {-1, -1};
for (auto i : v) {
mx = max(mx, {dist[u][i], i});
}
u = mx[1];
ans.push_back(u);
vector<int> newv;
for (auto i : v) {
if (i == u) continue;
newv.push_back(i);
}
v = newv;
}
return ans;
}
vector<int> createFunTour(int _n, int q) {
n = _n;
if (n <= 500) {
return solve();
}
for (int i = 1; i <= n; i++) {
rem.insert(i);
}
solve(1);
for (auto &i : ans) i--;
if (!check(ans)) {
return solve();
}
return ans;
}
