#include "fun.h"
#include "bits/stdc++.h"
using namespace std;
std::vector<int> createFunTour(int n, int q) {
vector dist(n, vector(n, 0));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
dist[i][j] = hoursRequired(i, j);
}
vector<int> pw(20, 1);
for (int i = 1; i < 20; i++) pw[i] = pw[i - 1] * 2;
auto rec = [&](auto &rec, int n) -> vector<int> {
if (n == 1) return {0};
if (n == 2) return {1, 0};
if (n == 3) return {2, 1, 0};
vector<int> down, ans;
int lg = 31 - __builtin_clz(n);
for (int i = pw[lg] - 1; i < n; i++) down.emplace_back(i);
// cout << n << ' ' << down.size() << endl;
if (down.size() > pw[lg - 1]) {
vector<int> vec1, vec2;
int others = down.size() - pw[lg - 1];
for (int i = 0; i < others; i++) {
vec2.emplace_back(down.back());
down.pop_back();
}
for (int i = 0; i < others; i++) {
vec1.emplace_back(down.back());
down.pop_back();
}
reverse(vec1.begin(), vec1.end());
reverse(vec2.begin(), vec2.end());
for (int i = 0; i < others; i++) {
ans.emplace_back(vec2.back());
vec2.pop_back();
if (i < others - 1) {
ans.emplace_back(vec1.back());
vec1.pop_back();
}
}
down.emplace_back(vec1.back());
}
if (down.empty()) {
for (int x: rec(rec, pw[lg] - 1)) ans.emplace_back(x);
return ans;
}
vector<int> top;
for (int i = pw[lg] - pw[lg - 2]; i < pw[lg]; i++) {
top.emplace_back(i - 1);
}
// cout << '\t';
// for (int x: top) cout << x << ' ';
// cout << endl;
if (down.size() + 1 <= top.size()) {
ans.emplace_back(down.back());
down.pop_back();
while (!down.empty()) {
ans.emplace_back(top.back());
top.pop_back();
ans.emplace_back(down.back());
down.pop_back();
}
auto ans2 = rec(rec, top.empty() ? pw[lg] - pw[lg - 2] - 1 : top.back() + 1);
for (int x: ans2) ans.emplace_back(x);
return ans;
}
int l = (down.size() - top.size() + 1) / 2 - 1;
int r = l + top.size() + 1;
for (int i = 0; i < top.size(); i++) {
ans.emplace_back(down[i + l + 1]);
ans.emplace_back(top[top.size() - i - 1]);
}
while (l >= 0) {
if (l + 1 > (int) down.size() - r) {
ans.emplace_back(down[l--]);
} else {
ans.emplace_back(down[r++]);
}
}
auto ans2 = rec(rec, pw[lg] - pw[lg - 2] - 1);
for (int x: ans2) ans.emplace_back(x);
return ans;
};
auto ans = rec(rec, n);
// for (int x: ans) cout << x << ' ';
// cout << endl;
return ans;
}
