#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100'000;
int n, mark[N + 10];
int ch[2][N + 10], cnt[N + 10];
int mxH[N + 10], h[N + 10];
vector<int> ans;
int getDis(int u, int v) {
return hoursRequired(u - 1, v - 1);
}
void buildTrie() {
for (int i = 1; i <= n; i++) {
int lc = i << 1, rc = i << 1 | 1;
if (lc <= n)
ch[0][i] = lc;
if (rc <= n)
ch[1][i] = rc;
mxH[i] = 1;
}
for (int i = n; i >= 1; i--) {
mxH[i] = max(mxH[ch[0][i]], mxH[ch[1][i]]) + 1;
cnt[i] = 1 + cnt[ch[0][i]] + cnt[ch[1][i]];
}
}
int goDown(int u) {
while (cnt[ch[0][u]] || cnt[ch[1][u]]) {
if (mxH[ch[1][u]] >= mxH[ch[0][u]])
u = ch[1][u];
else
u = ch[0][u];
}
return u;
}
int calcFirst(int u, int t = 0) {
int p = (u == 1? 0: calcFirst(u / 2, u % 2));
if (p != u / 2)
return p;
if (cnt[ch[0][u]] && cnt[ch[1][u]])
return goDown(ch[t ^ 1][u]);
return u;
}
int getFar(int u) {
vector<pair<pair<int, int>, int>> vec;
pair<int, int> bestCase = {1, u / 2};
int pnt = u, disTmp = 0;
while (pnt != 1) {
int t = 1 - pnt % 2;
if (cnt[ch[t][pnt / 2]]) {
int now = mxH[ch[t][pnt / 2]] + disTmp + 1;
if (now > bestCase.first)
bestCase = {now, ch[t][pnt / 2]};
}
disTmp++;
pnt /= 2;
}
if (bestCase.second == u / 2)
return u / 2;
return goDown(bestCase.second);
}
void del(int u) {
cnt[u]--;
mxH[u] = 0;
u /= 2;
while (u) {
int i = u;
mxH[i] = max(mxH[ch[0][i]], mxH[ch[1][i]]) + 1;
cnt[i] = 1 + cnt[ch[0][i]] + cnt[ch[1][i]];
u /= 2;
}
}
void solve() {
buildTrie();
int u = n;
for (int i = 1; i <= n; i++) {
ans.push_back(u);
//cout << i << ": " << u << endl;
if (i != n) {
int last = u;
u = getFar(u);
del(last);
}
}
}
vector<int> createFunTour(int N, int Q) {
n = N;
solve();
for (int i = 0; i < n; i++)
ans[i]--;
return ans;
}
