#include "fun.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define s second
#define MNTO(x,y) x=min(x,y)
#define ALL(x) x.begin(),x.end()
using namespace std;
const int maxn=1e5+5;
#define REP(i,n) for(int i=0;i<n;i++)
int d[maxn],p[maxn];
vector<int> t[maxn];
bool cmp(int a,int b){
return d[a]<d[b];
}
bool cmp2(int a,int b){
return sz(t[a])>sz(t[b]);
}
bool cmp3(int a,int b){
return d[t[a].back()]>d[t[b].back()];
}
vector<int> createFunTour(int n, int q) {
pii mn={INT_MAX,-1};
REP(i,n){
int sz=attractionsBehind(0,i);
if(sz>n/2) MNTO(mn,make_pair(sz,i));
}
int c=mn.s;
vector<int> v;
REP(i,n){
d[i]=hoursRequired(c,i);
if(d[i]==1) v.pb(i);
}
REP(i,n){
if(i==c) continue;
while(p[i]<sz(v)-1 and hoursRequired(v[p[i]],i)>d[i]) ++p[i];
t[p[i]].pb(i);
}
int ord[3]={0,1,2};
REP(i,3) sort(ALL(t[i]),cmp);
sort(ord,ord+3,cmp2);
vector<int> ans;
int pv=-1;
while(sz(t[ord[0]])<sz(t[ord[1]])+sz(t[ord[2]])){
sort(ord,ord+3,cmp3);
int i=(pv==ord[0]);
ans.pb(t[ord[i]].back());
t[ord[i]].pop_back();
pv=ord[i];
sort(ord,ord+3,cmp2);
}
t[ord[1]].insert(t[ord[1]].end(),ALL(t[ord[2]]));
sort(ALL(t[ord[1]]),cmp);
int st=0;
if(sz(ans) and d[ans.back()]<d[t[ord[1]].back()]) st=1;
while(sz(t[ord[st]])){
ans.pb(t[ord[st]].back());
t[ord[st]].pop_back();
st=1-st;
}
ans.pb(c);
return ans;
}
