#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
mt19937 rnd(228);
vector<int> Solve(int n) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
shuffle(ord.begin(), ord.end(), rnd);
map<pair<int, int>, bool> asked;
auto ask = [&](int i, int j) {
if (!asked.count({i, j})) {
asked[{i, j}] = Query(i, j);
asked[{j, i}] = !asked[{i, j}];
}
return asked[{i, j}];
};
stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
return !ask(i, j);
});
// auto merge_sort = [&](auto self, vector<int> a) -> vector<int> {
// if (a.size() == 1) {
// return a;
// }
// int mid = a.size() / 2;
// auto L = self(self, vector(a.begin(), a.begin() + mid));
// auto R = self(self, vector(a.begin() + mid, a.end()));
// a.clear();
// int i = 0, j = 0;
// while (i < L.size() || j < R.size()) {
// if (i < L.size() && (j == R.size() || !ask(L[i], R[j]))) {
// a.push_back(L[i++]);
// } else {
// a.push_back(R[j++]);
// }
// }
// return a;
// };
//
// ord = merge_sort(merge_sort, ord);
auto is_n = [&](int i) {
int killer = -1;
int skipped = 0;
for (int k = 0; k < n && skipped < 2; ++k) {
if (k == i) continue;
if (ask(ord[i], ord[k])) {
} else {
++skipped;
killer = k;
}
}
if (skipped == 1) {
int kek = 0;
skipped = 0;
for (int k = 0; k < i && skipped < 2; ++k) {
if (k == i) continue;
if (k != killer) {
bool now = ask(ord[killer], ord[k]);
if (!now) {
skipped += 1;
}
}
}
if (skipped == 1) {
return true;
}
}
return false;
};
bool damn = false;
for (int i = n - 1; i > 0;) {
if (i == n - 1) {
if (is_n(i)) {
--i;
continue;
}
}
if (damn || i + 1 < n && ask(ord[i], ord[i + 1])) {
--i;
damn = false;
continue;
}
damn = false;
int j = i - 2;
while (j >= 0 && ask(ord[j], ord[i])) {
--j;
}
if (i - j > 3 && ask(ord[i - 1], ord[j + 1])) {
++j;
damn = true;
} else if (i - j == 3) {
if (i == n - 1) {
if (is_n(i - 1)) {
swap(ord[i], ord[i - 1]);
} else {
swap(ord[i - 2], ord[i]);
}
} else {
if (ask(ord[i - 1], ord[i + 1])) {
swap(ord[i], ord[i - 1]);
} else {
swap(ord[i - 2], ord[i]);
}
}
i -= 3;
continue;
}
reverse(ord.begin() + j + 1, ord.begin() + i + 1);
i = j;
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[ord[i]] = i;
}
return ans;
}
