#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
std::vector<int> Solve(int N) {
std::vector<int> arr;
// vector<vector<int>> triangles;
vector<vector<int>> data(N);
for (int i = 0; i < N; i++) {
// for (int v : arr) cout << S[v] << ' ';
// cout << '\n';
// cout << "----------\n";
// for (vector<int> v : triangles) {
// for (int c : v)
// cout << S[c] << ' ';
// cout << '\n';
// }
// cout << endl;
int ins_ind = 0;
// if (!arr.empty() && !Query(arr[0], i))
ins_ind = lower_bound(arr.begin(), arr.end(), i, [&](ll a, ll b){return Query(b, a);}) - arr.begin();
if (2 <= ins_ind && data[arr[ins_ind-1]].empty() && data[arr[ins_ind-2]].size() < 5 && !Query(i, arr[ins_ind - 2])) {
vector<int>& v = data[arr[ins_ind-2]];
if (v.empty()) {
v = {i, arr[ins_ind - 1], arr[ins_ind - 2]};
} else {
if (Query(i, v[1])) {
v = {v[0], v[1], v[2], i, arr[ins_ind - 1]};
} else {
v = {i, arr[ins_ind - 1], v[2], v[0], v[1]};
}
}
arr.erase(arr.begin() + ins_ind - 1);
} else if (ins_ind + 1 < arr.size() && data[arr[ins_ind]].empty() && data[arr[ins_ind+1]].size() < 5 && Query(i, arr[ins_ind + 1])) {
vector<int>& v = data[arr[ins_ind+1]];
if (v.empty()) {
v = {arr[ins_ind], i, arr[ins_ind + 1]};
} else {
if (Query(i, v[1])) {
v = {v[0], v[1], v[2], arr[ins_ind], i};
} else {
v = {arr[ins_ind], i, v[2], v[0], v[1]};
}
}
arr.erase(arr.begin() + ins_ind);
} else {
arr.insert(arr.begin() + ins_ind, i);
}
}
// for (int c : arr) cout << S[c] << ' ';
// cout << "\n-------------\n";
// for (int c : arr) {
// for (int v : data[c]) cout << S[v] << ' ';
// cout << '\n';
// }
// cout << "-------------\n";
vector<vector<int>> rarr;
for (int v : arr) {
if (data[v].empty()) {
if (!rarr.empty() && (rarr.back().size() == 3) && !Query(v, rarr.back()[0])) {
if (Query(v, rarr.back()[1]))
rarr.back() = {rarr.back()[1], rarr.back()[2], rarr.back()[0], v};
else
rarr.back() = {v, rarr.back()[2], rarr.back()[0], rarr.back()[1]};
} else
rarr.push_back({v});
} else {
if (!rarr.empty() && (rarr.back().size() == 1 || rarr.back().size() == 3) && data[v].size() == 3 && !Query(data[v][0], rarr.back()[0]) && !Query(data[v][1], rarr.back()[0])) {
if (rarr.back().size() == 1) {
rarr.back() = {data[v][0], data[v][1], data[v][2], rarr.back()[0]};
} else {
rarr.back() = {data[v][0], data[v][1], data[v][2], rarr.back()[2], rarr.back()[0], rarr.back()[1]};
}
}
else
rarr.push_back(data[v]);
}
}
for (int i = 0; i + 1 < rarr.size(); i++) {
if (rarr[i].size() == 1 && rarr[i+1].size() == 1) {
rarr[i] = {rarr[i+1][0], rarr[i][0]};
rarr[i+1].clear();
}
}
// for (vector<int> d : rarr) {
// for (int c : d) cout << S[c] << ' ';
// cout << '\n';
// }
arr.clear();
bool unsure = true;
for (vector<int> d : rarr) {
if (d.empty()) continue;
if (d.size() != 3) {
if (!arr.empty() && unsure) {
assert(arr.size() == 3);
for (int a = 0; a < 3; a++) {
arr = {arr[2], arr[0], arr[1]};
if (Query(arr[2], d[0])) {
arr.insert(arr.end(), d.begin(), d.end());
unsure = false;
goto OUT;
}
}
}
arr.insert(arr.end(), d.begin(), d.end());
unsure = false;
} else {
if (arr.empty()) arr = d;
else {
if (unsure) {
assert(arr.size() == 3);
for (int a = 0; a < 3; a++) {
arr = {arr[2], arr[0], arr[1]};
for (int b = 0; b < 3; b++) {
d = {d[2], d[0], d[1]};
if (Query(arr[2], d[0])) {
arr.insert(arr.end(), d.begin(), d.end());
unsure = false;
goto OUT;
}
}
}
} else {
for (int b = 0; b < 2; b++) {
d = {d[2], d[0], d[1]};
if (Query(arr.back(), d[0])) {
arr.insert(arr.end(), d.begin(), d.end());
goto OUT;
}
}
d = {d[2], d[0], d[1]};
arr.insert(arr.end(), d.begin(), d.end());
}
}
}
OUT:;
}
// for (int v : arr) cout << S[v] << ' ';
// cout << '\n';
vector<int> T(N);
for (int i = 0; i < N; i++) T[arr[i]] = i;
// cout << "----------\n";
// for (vector<int> v : triangles) {
// for (int c : v)
// cout << S[c] << ' ';
// cout << '\n';
// }
return T;
}
