#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int rt, pa[nx], lvl[nx], n;
vector<int> res, d[nx];
set<pair<int, int>> s[nx];
pair<int, int> mx, hd;
pair<int, int> getmax(int x)
{
if (s[x].empty()) return {-1, -1};
return *(prev(s[x].end()));
}
void findmax(int x)
{
auto tmp=getmax(x);
tmp.first-=lvl[x];
mx=max(mx, tmp);
int u=x;
while (u!=0)
{
int t=pa[u];
for (auto v:d[t])
{
if (v==u) continue;
pair<int, int> tmp=getmax(v);
tmp.first-=lvl[v];
tmp.first+=lvl[x]-lvl[t]+1;
mx=max(mx, tmp);
}
u=t;
if (s[u].find({lvl[u], u})!=s[u].end()) mx=max(mx, {lvl[x]-lvl[u], u});
}
}
void addnode(int x)
{
int u=x;
s[u].insert({lvl[u], u});
while (u!=0) u=pa[u], s[u].insert({lvl[x], x});
}
void erasenode(int x)
{
int u=x;
s[u].erase({lvl[u], u});
while (u!=0) u=pa[u], s[u].erase({lvl[x], x});
}
struct segtree
{
pair<int, int> d[4*nx];
void update(int l, int r, int i, int idx, int vl)
{
if (idx<l||r<idx) return;
if (l==r) return d[i]={vl, idx}, void();
int md=(l+r)/2;
update(l, md, 2*i, idx,vl);
update(md+1, r, 2*i+1, idx, vl);
d[i]=max(d[2*i], d[2*i+1]);
}
pair<int, int> query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return {INT_MIN, INT_MIN};
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} st;
void buildtree(int i, int l, int r)
{
if (i!=l)
{
auto tmp=st.query(0, n-1, 1, l, i-1);
d[i].push_back(tmp.second);
pa[tmp.second]=i;
lvl[tmp.second]=lvl[i]+1;
buildtree(tmp.second, l, i-1);
}
if (i!=r)
{
auto tmp=st.query(0, n-1, 1, i+1, r);
d[i].push_back(tmp.second);
pa[tmp.second]=i;
lvl[tmp.second]=lvl[i]+1;
buildtree(tmp.second, i+1, r);
}
}
std::vector<int> createFunTour(int N, int Q) {
n=N;
for (int i=1; i<N-1; i++) hd=max(hd, {attractionsBehind(i-1, i)+attractionsBehind(i+1, i), i});
if (hd.first==N+1) rt=hd.second;
else
{
if (hoursRequired(0, hd.second)!=1) rt=N-1;
else if (hoursRequired(N-1, hd.second)!=1) rt=0;
else
{
int tmp;
for (int i=1; i<N-1; i++) if (hoursRequired(i, hd.second)==1) tmp=i;
if (tmp<hd.second) rt=0;
else rt=N-1;
}
}
for (int i=0; i<N; i++) st.update(0, N-1, 1, i, attractionsBehind(rt, i));
buildtree(rt, 0, N-1);
for (int i=0; i<N; i++) addnode(i);
for (int i=0; i<N;i ++) mx=max(mx, {lvl[i], i});
rt=mx.second;
res.push_back(rt);
erasenode(rt);
for (int i=1; i<N; i++)
{
mx={-1, -1};
findmax(rt);
res.push_back(mx.second);
erasenode(mx.second);
rt=mx.second;
}
return res;
}
