#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> my_sort(vector<int> nw) {
map<pair<int, int>, int> vl;
map<int, int> cnt;
for (int i = 0; i < (int)nw.size(); ++i) {
for (int j = i + 1; j < (int)nw.size(); ++j) {
if (Query(nw[i], nw[j])) {
vl[{nw[i], nw[j]}] = 1;
cnt[nw[i]]++;
} else {
vl[{nw[j], nw[i]}] = 1;
cnt[nw[j]]++;
}
}
}
int start;
for (int i = 0; i < (int)nw.size(); ++i) {
if (cnt[nw[i]] == 1) {
bool check = true;
for (int j = 0; j < (int)nw.size(); ++j) {
if (vl[{nw[i], nw[j]}] && cnt[nw[j]] != 1) {
check = false;
break;
}
}
if (check) {
start = nw[i];
break;
}
}
}
vector<int> ans = {start};
set<int> used = {start};
while (ans.size() < nw.size()) {
for (int i = 0; i < (int)nw.size(); ++i) {
if (!used.count(nw[i]) && vl[{ans.back(), nw[i]}]) {
ans.push_back(nw[i]);
used.insert(nw[i]);
break;
}
}
}
return ans;
}
vector<int> Solve(int n) {
vector<int> ord = {0};
for (int i = 1; i < n; ++i) {
int l = -1, r = ord.size();
while (l < r - 1) {
int m = (l + r) / 2;
if (Query(i, ord[m])) {
l = m;
} else {
r = m;
}
}
vector<int> ord_nw;
for (int j = 0; j <= l; ++j) {
ord_nw.push_back(ord[j]);
}
ord_nw.push_back(i);
for (int j = r; j < (int)ord.size(); ++j) {
ord_nw.push_back(ord[j]);
}
ord = ord_nw;
}
// for (int i = 0; i < n; ++i) {
// cout << ord[i] << ' ';
// }
// cout << endl;
int pos = 0;
vector<int> poses;
while (pos < n - 2) {
int r = pos + 2;
if (Query(ord[pos], ord[r])) {
while (r + 1 < n && Query(ord[pos], ord[r + 1])) {
r++;
}
if (r == pos + 2) {
poses.push_back(pos);
} else {
if (Query(ord[pos + 1], ord[r])) {
reverse(ord.begin() + pos, ord.begin() + r + 1);
} else {
reverse(ord.begin() + pos, ord.begin() + r);
}
}
} else {
while (r + 1 < n && Query(ord[r + 1], ord[pos])) {
r++;
}
if (r > pos + 2) {
if (Query(ord[r], ord[pos + 1])) {
reverse(ord.begin() + pos, ord.begin() + pos + 2);
reverse(ord.begin() + pos + 2, ord.begin() + r + 2);
r++;
} else {
reverse(ord.begin() + pos + 1, ord.begin() + r + 2);
r++;
}
} else {
vector<int> vals = {ord[pos], ord[pos + 1], ord[pos + 2], ord[pos + 3]};
vals = my_sort(vals);
ord[pos] = vals[0];
ord[pos + 1] = vals[1];
ord[pos + 2] = vals[2];
ord[pos + 3] = vals[3];
r++;
}
}
pos = r + 1;
}
if (pos == n - 2) {
swap(ord[n - 2], ord[n - 1]);
}
for (int i = 0; i < (int)poses.size(); ++i) {
if (poses[i] == -1) {
continue;
}
if (poses[i] != 0) {
vector<int> vals = {ord[poses[i] - 1], ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2]};
vals = my_sort(vals);
ord[poses[i]] = vals[1];
ord[poses[i] + 1] = vals[2];
ord[poses[i] + 2] = vals[3];
} else if (i + 1 == (int)poses.size() || poses[i] + 3 != poses[i + 1]) {
vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3]};
vals = my_sort(vals);
ord[poses[i]] = vals[0];
ord[poses[i] + 1] = vals[1];
ord[poses[i] + 2] = vals[2];
} else {
vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3], ord[poses[i] + 4], ord[poses[i] + 5]};
vals = my_sort(vals);
ord[poses[i]] = vals[0];
ord[poses[i] + 1] = vals[1];
ord[poses[i] + 2] = vals[2];
ord[poses[i] + 3] = vals[3];
ord[poses[i] + 4] = vals[4];
ord[poses[i] + 5] = vals[5];
poses[i + 1] = -1;
}
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[ord[i]] = i;
}
return ans;
}
