#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTour(int N, int Q){
int lst[N + 1];
int d[N + 1];
int d1[N + 2][2];
set<pair<int,int>,greater<pair<int,int>>> sat[3];
for(int i = 0; i < N; i++){
lst[i] = attractionsBehind(0,i);
}
pair<int,int> ii = {N + 90,-1};
for(int i = 0; i < N; i++){
if(lst[i] >= (N+1)/2 ) ii = min(ii,{lst[i],i});
}
int it = ii.second;
for(int i = 0; i < N; i++){
d[i] = hoursRequired(it,i);
}
vector<int> tee;
for(int i = 0; i < N; i++){
if(d[i] == 1) tee.push_back(i);
}
if(tee.size() == 1){
return {0,1};
}
else{
for(int i = 0; i < N; i++){
d1[i][0] = hoursRequired(i,tee[0]);
d1[i][1] = hoursRequired(i,tee[1]);
}
for(int i = 0; i < N; i++){
if(i == it) continue;
if(d1[i][0] < d[i]){
sat[0].insert({d[i],i});
}
else if(d1[i][1] < d[i]){
sat[1].insert({d[i],i});
}
else sat[2].insert({d[i],i});
}
int prev = -1;
vector<int> ans = {};
while(true){
//assert (!(sat[0].empty()) && !(sat[1].empty()) && !(sat[2].empty()));
if(max(max(sat[0].size(),sat[1].size() ), sat[2].size()) >= N/2){
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].begin() -> first,i});
if(ii.second == prev) break;
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
break;
}
if(prev == -1){
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].begin() -> first,i});
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
else{
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) if(i != prev) ii = max(ii, {sat[i].begin() -> first,i});
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
}
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].size(),i});
int fat = ii.second;
bool die = false;
while(sat[0].size() + sat[1].size() + sat[2].size() > 0){
if(prev != fat){
prev = fat;
if(sat[fat].empty()){
die = true;
ans.push_back(it);
if(!sat[1].empty()) ans.push_back(sat[1].begin() -> second);
if(!sat[2].empty()) ans.push_back(sat[2].begin() -> second);
if(!sat[0].empty()) ans.push_back(sat[0].begin() -> second);
break;
}
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
else{
ii = {-10,-1};
for(int i = 0; i < 3; i++) if(i != prev && !sat[i].empty())ii = max(ii, {sat[i].begin() -> first,i});
if(ii.second == -1){
die = true;
ans.push_back(it);
ans.push_back(sat[fat].begin() -> second);
break;
}
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
}
if(!die) ans.push_back(it);
return ans;
}
}
