#include "fun.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> createFunTour(int N, int Q) {
vector<int> per(N);
if(N==2){
per[0]=0;
per[1]=1;
return per;
}
int cnt=0;
int cur=0;
int cn=N;
vector<int> sp(100001);
int ff=3;
int fg=1;
while(ff<=100000){
sp[ff]=fg;
fg=fg*2+2;
ff=ff*2+1;
}
while(cnt<N){
vector<int> bf1;
vector<int>bf2;
queue<int> q;
if(cur*2+2>=cn){
if(cur*2+1>=cn){
per[cnt]=cur;
cnt++;
}
else{
per[cnt]=cur*2+1;
cnt++;
per[cnt]=cur;
cnt++;
}
break;
}
q.push(cur*2+2);
while(!q.empty()){
int u=q.front();
bf2.push_back(u);
q.pop();
if(u*2+1<cn)q.push(u*2+1);
if(u*2+2<cn)q.push(u*2+2);
}
reverse(bf2.begin(),bf2.end());
if(bf2[0]==cn-1){
q.push(cur*2+1);
while(!q.empty()){
int u=q.front();
bf1.push_back(u);
q.pop();
if(u*2+1<cn)q.push(u*2+1);
if(u*2+2<cn)q.push(u*2+2);
}
reverse(bf1.begin(),bf1.end());
bf1.push_back(cur);
int i=0;
int j=0;
bool ch=false;
while(cnt<N){
per[cnt]=bf1[i];
i++;
cnt++;
if(cnt==N)break;
if(!ch){
per[cnt]=bf2[j];
j++;
cnt++;
if(j==bf2.size()){
ch=true;
j=bf1.size()-1;
}
}
else{
per[cnt]=bf1[j];
j--;
cnt++;
}
}
}
else{
bf2.push_back(cur);
for(int j=0;j<bf2.size();j++){
per[cnt]=cn-1;
if(sp[cn-1]!=0){
cn=sp[cn-1]+2;
}
cn--;
cnt++;
per[cnt]=bf2[j];
cnt++;
}
cur=2*cur+1;
}
}
return per;
}
