#include<bits/stdc++.h>
#include "fun.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t)){
cerr<<", ";
}
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5+5;
struct node{
int id, gleb=0;
node* l=nullptr, *r=nullptr, *par=nullptr;
node(int id): id(id){}
};
bool czy[N];
int gleb[N];
int find_dist(node* v){
//deb("a");
if(!v->par)return 0;
if(v==v->par->l){
if(v->par->r)return max(find_dist(v->par)+1, v->par->r->gleb+2);
else return find_dist(v->par)+1;
}
else{
//deb(v->id);
if(v->par->l)return max(find_dist(v->par)+1, v->par->l->gleb+2);
else return find_dist(v->par)+1;
}
}
void upd(node*v){
v->gleb=0;
if(v->l)v->gleb=v->l->gleb+1;
if(v->r)v->gleb=max(v->gleb, v->r->gleb+1);
}
node* find(node* v, int dist, int t){
//deb("c");deb(v, dist, t);
if(v){
//deb(v, dist, t)
}
//deb(v->id, dist);
if(dist==0)return v;
if(t){
if(v->l && v->l->gleb==dist-1)return find(v->l, dist-1, 1);
else return find(v->r, dist-1, 1);
}
if(v==v->par->l && v->par->r && dist==v->par->r->gleb+2)return find(v->par->r, dist-2, 1);
if(v==v->par->r && v->par->l && dist==v->par->l->gleb+2)return find(v->par->l, dist-2, 1);
return find(v->par, dist-1, 0);
}
vector<node*> nodes;
vi dep;
node* solve(int l, int r){
if(l>r)return 0;
int m=l;
for(int i=l; i<=r; i++){
if(dep[i]<dep[m])m=i;
}
node* u=solve(l, m-1), *v=solve(m+1, r);
nodes[m]->l=u;
nodes[m]->r=v;
if(v)v->par=nodes[m];
if(u)u->par=nodes[m];
upd(nodes[m]);
return nodes[m];
}
std::vector<int> createFunTour(int n, int Q) {
//int H = hoursRequired(0, N - 1);
//int A = attractionsBehind(0, N - 1);
vi V={0};
int dd=hoursRequired(0, n - 1);
for(int i=1; i<n-1; i++){
if(hoursRequired(0, i)+hoursRequired(i, n - 1)==dd){
V.pb(i);
}
}
V.pb(n-1);
int l=n, r=-1;
for(int i:V){
if(i!=n-1 && attractionsBehind(i+1, i)!=i+1)r=max(r, i+1);
if(i && attractionsBehind(i-1, i)!=n-i)l=min(l, i-1);
}
int t=-1;
for(int i:V){
if(i<=l && i>=r){
t=i;
break;
}
}
deb(t, l, r, V.size());
dep.resize(n);
for(int i=0; i<n; i++){
dep[i]=hoursRequired(t, i);
}
for(int i=0; i<n; i++){
nodes.pb(new node(i));
}
vi ans;
node* root=solve(0, n-1);
/*for(int i=0; i<n; i++){
deb(i, nodes[i]->id, nodes[i]->gleb);
node*v=nodes[i];
if(v->l){deb(v->l->id);}
if(v->r){deb(v->r->id);}
if(v->par){deb(v->par->id);}
}*/
ans.pb(find(root, root->gleb, 1)->id);
while(ans.size()<n){
//deb(ans.back());
if(ans.back()==root->id){
//deb("a");
int d=root->gleb;
node*v=find(root, d, 1);
if(root->l==0){
root->r->par=0;
root=root->r;
}
else{
root->l->par=0;
root=root->l;
}
ans.pb(v->id);
}
else{
node*v=nodes[ans.back()];
int d=find_dist(v);
node*u=find(v, d, 0);
//deb(v->id, u->id, d);
if(v==v->par->l)v->par->l=0;
else v->par->r=0;
while(v->par){
v=v->par;
upd(v);
}
ans.pb(u->id);
}
}
return ans;
}
