#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
set<pair<int, int>> s[N];
bool ch[N];
vector<int> createFunTour(int _N, int Q) {
n = _N;
for (int i = n - 1;i >= 0;i--) {
s[i].insert({ 0, i });
if (2 * i + 1 < n) {
for (auto& [d, j] : s[2 * i + 1]) s[i].insert({ d + 1, j });
}
if (2 * i + 2 < n) {
for (auto& [d, j] : s[2 * i + 2]) s[i].insert({ d + 1, j });
}
}
vector<int> res;
res.push_back(n - 1);
while ((int)res.size() < n) {
int now = res.back();
ch[now] = 1;
auto x1 = (--s[now].end());
int d = 0;
int mx = x1->first, idx = x1->second;
s[now].erase({ 0, now });
while (now != 0) {
int p = (now - 1) / 2;
if (ch[p]) break;
s[p].erase({ ++d, res.back() });
int dis = d, id = 0;
if (now == 2 * p + 1) {
if (s[now + 1].empty()) id = p;
else {
auto x = --s[now + 1].end();
dis += x->first, id = x->second;
}
}
else {
if (s[now - 1].empty()) id = p;
else {
auto x = --s[now - 1].end();
dis += x->first, id = x->second;
}
}
if (dis > mx) {
mx = dis;
idx = id;
}
now = p;
}
res.push_back(idx);
}
return res;
}
