#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
pii p ;
int cur , mark[maxn] , n , H[4 * maxn] , val[4 * maxn] , X , pt;
set<pii> seg[4 * maxn] ;
void build(int x = 0 , int lx = 0 , int rx = pt , int h = 1 ){
H[x] = h ;
seg[x].insert({-h , x}) ;
//cout<<x <<" : " << H[x] <<" boom " << endl ;
int mid = lx + rx >> 1 ;
if(2 * x + 1 < n){
build( 2 * x + 1 , lx , mid , h + 1) ;
for(auto u : seg[x * 2 + 1]) seg[x].insert(u) ;
}
if(2 * x + 2 < n){
build(2 * x + 2 , mid , rx , h + 1) ;
for(auto u : seg[x * 2 + 2]) seg[x].insert(u) ;
}
// cout<<x <<" : " ; for(auto u : seg[x]) cout<<u.X <<"," << u.Y <<" " ; cout<<endl ;
// sort(all(seg[x])) ;
}
void del(int x){
seg[x].erase({-H[X] , X}) ;
if(x == 0) return ;
x = (x - 1) / 2 ;
del(x) ;
}
pii dfs(int v){
int x , V = v ;;
p = {0 , 0} ;
if(v == 0 ){
p = {seg[0].begin() -> X - 1 , seg[0].begin() -> Y} ;
return p ;
}
while(v != 0){
// cout<<"DFS : " << v <<" , " << V << endl ;
x = v ;
v = (v - 1) / 2 ;
if(x & 1) x = 2 * v + 2 ;
else x = 2 * v + 1 ;
if(SZ(seg[x])) p = max(p ,{ H[V] + (-1 * (seg[x].begin() -> X) ) - 2 * H[v] , seg[x].begin() -> Y } ) ;
}
return p ;
}
vec<int> ans ;
vec<int> createFunTour(int N , int Q){
n = N ;
pt = 1 ;
while(pt < n ) pt *= 2 ;
build() ;
ans.pb(seg[1].begin() -> Y) ;
while(SZ(ans) < n){
//cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl ;
X = ans.back() ;
del(ans.back()) ;
ans.pb(dfs(ans.back()).Y) ;
}
// for(int i = 0 ; i < n ; i ++ ) ans[i] = val[ans[i]] ;
return ans ;
}
/*int main()
{
migmig ;
cin>>n ;
pt = 1 ;
while(pt < n ) pt *= 2 ;
build() ;
ans.pb(seg[1].begin() -> Y) ;
while(SZ(ans) < n){
// cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl ;
X = ans.back() ;
del(ans.back()) ;
ans.pb(dfs(ans.back()).Y) ;
}
// for(int i = 0 ; i < n ; i ++ ) ans[i] = val[ans[i]] ;
for(auto u : ans) cout<<u <<" " ;
}*/
