#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a),end(a)
#define sz(a) (int)a.size()
#define pb push_back
const int mxN = (int)1e5+10;
vector<int> ans;
bool vis[mxN];
set<pair<int,int>> S[mxN];
void add(int x){
ans.pb(x-1); vis[x]=true;
//cout << x << " ";
// remove x from the tree
int par = x, dis = 0;
while(par){
S[par].erase({dis,x});
if(par==1) break;
par/=2, dis++;
}
}
int find_farthest(int x){
int par = x/2, pre=x, pre2=-1;
while(par){
if(vis[par]) break;
if(par==1) break;
pre2 = pre; pre=par; par/=2;
}
int other_subtree;
if(vis[par]){
par = pre;
other_subtree = par*2;
if(pre2==other_subtree) other_subtree++;
}
else{
other_subtree = par*2;
if(pre==other_subtree) other_subtree++;
}
if(vis[other_subtree]) return par;
return prev(end(S[other_subtree]))->second;
}
vector<int> createFunTour(int N, int Q) {
if(N==2) return {1,0};
ans.clear(); vis[0]=1;
for(int i = 1; i <= N; i++){
int par = i, dis = 0;
while(par){
S[par].insert({dis,i});
if(par==1) break;
par/=2, dis++;
}
}
int x = N; add(x);
while(sz(ans)!=N) x = find_farthest(x), add(x);
return ans;
}
