#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int get(vector<pii>& furthest, int v){
pii best = {-1, -1};
int l = 1;
while(v > 0){
best = max(best, {(v-1)/2, l});
if(v&1) best = max(best, {furthest[v+1].first + l + 1, furthest[v+1].second});
else best = max(best, {furthest[v-1].first + l + 1, furthest[v-1].second});
l++, v = (v-1)/2;
}
return best.second;
}
void rem(vector<pii>& furthest, int v){
furthest[v] = {-1e9, -1};
while(v > 0){
if(v&1) furthest[(v-1)/2] = max(furthest[v], furthest[v+1]);
else furthest[(v-1)/2] = max(furthest[v], furthest[v-1]);
furthest[(v-1)/2].first++;
furthest[(v-1)/2] = max(furthest[(v-1)/2], {0, (v-1)/2});
v = (v-1)/2;
}
}
vector<int> createFunTour(int N, int Q) {
/*if(N <= 500){
vector<vector<int> > t(N, vector<int>(N));
pii start = {-1, 0};
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++) t[i][j] = hoursRequired(i,j), start = max(start, {t[i][j], i});
vector<bool> alive(N, true);
int poz = start.second;
vector<int> ans(N, 0);
for(int x = 0; x < N; x++){
ans[x] = poz;
alive[poz] = false;
pii best = {-1, 0};
for(int i = 0; i < N; i++)
if(alive[i]) best = max(best, {t[poz][i], i});
poz = best.second;
}
return ans;
}*/
vector<pii> furthest(N, {-1, -1});
for(int i = 0; i < N; i++){
int l = 0, v = i;
furthest[i] = {0,i};
while(v > 0){
furthest[(v-1)/2] = max(furthest[(v-1)/2], {++l, i});
v = (v-1)/2;
}
}
int poz = N-1;
vector<int> ans(N, 0);
for(int x = 0; x < N; x++){
ans[x] = poz;
int uj = get(furthest, poz);
rem(furthest, poz);
poz = uj;
}
ans[N-1] = 0;
return ans;
}
/*int main(){
int N;
cin>>N;
vector<int> a = createFunTour(N, -1);
for(int& b : a) cout<<b<<" ";
cout<<"\n";
}*/
