#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> ans;
int queries[1005][1005];
int query(int a, int b) {
if(queries[a][b] == -1) queries[a][b] = Query(a, b);
return queries[a][b];
}
void conquer(int l_l, int l_r, int r_l, int r_r) {
queue<int> a, b;
for(int i = l_l; i <= l_r; i++) a.push(ans[i]);
for(int i = r_l; i <= r_r; i++) b.push(ans[i]);
queue<int> c;
while(!a.empty() && !b.empty()) {
if(query(b.front(), a.front())) {
c.push(a.front());
a.pop();
} else {
c.push(b.front());
b.pop();
}
}
while(!b.empty()) {
c.push(b.front());
b.pop();
}
while(!a.empty()) {
c.push(a.front());
a.pop();
}
for(int i = l_l; i <= r_r; i++) {
ans[i] = c.front();
c.pop();
}
// for(auto i : ans) cout << i << ' '; cout << '\n';
}
void divide(int l, int r) {
if(l != r) {
int m = (l+r)/2;
divide(l, m);
divide(m+1, r);
conquer(l, m, m+1, r);
}
}
vector<int> Solve(int n) {
memset(queries, -1, sizeof(queries));
ans = vector<int>(n, 0);
for(int i = 0; i < n; i++) ans[i] = i;
divide(0, n-1);
vector<pair<int, int>> revranges;
bool first = true;
for(int i = 3; i < min(500, n) && first; i++) first &= query(ans[i], ans[1]);
int p1 = 0, p2 = 2;
if(!first) {
revranges.push_back(make_pair(0, 0));
p1 = 1, p2 = 3;
}
// for(auto i : ans) cerr << i << ' '; cerr << '\n';
while(p1 < n) {
if(p2 >= n) {
revranges.push_back(make_pair(p1, min(n-1, p2)));
break;
}
while(query(ans[p1], ans[p2]) && p2 < n) {
p2++;
if(p2 == n) break;
}
p2--;
revranges.push_back(make_pair(p1, p2));
// cerr << p1 << ' ' << p2 << '\n';
p1 = p2 + 1;
p2 = p1 + 2;
}
// if(query(revranges[0].first, revranges[0].second)) {
// revranges[0].first++;
// revranges.insert(revranges.begin(), make_pair(0, 0));
// }
// for(auto i : revranges) cerr << i.first << ' ' << i.second << '\n';
vector<int> actualAns(n, -1);
auto full = [&](pair<int, int> &x){
// printf("full\n\n");
for(int j = x.first; j <= x.second; j++) actualAns[x.second - j + x.first] = ans[j];
};
auto some = [&](pair<int, int> &x){
// printf("some\n\n");
for(int j = x.first; j < x.second; j++) actualAns[x.second - j + x.first - 1] = ans[j];
actualAns[x.second] = ans[x.second];
};
for(auto &i : revranges) {
if(i.first == i.second) {
actualAns[i.first] = ans[i.first];
continue;
}
// printf("%d to %d:\n", i.first, i.second);
if(i.second - i.first > 1) {
if (i.second - i.first != 2) { // range is length 3
// printf("%d vs %d\n", i.first + 1, i.second);
if(query(ans[i.second], ans[i.first + 1])) some(i);
else full(i);
}
} else full(i);
}
for(int i = 0; i < revranges.size(); i++) {
pair<int, int> x = revranges[i];
if(x.second - x.first == 2) {
// putang ina MO
// length 3 penis dick
// printf("%d %d: \n", x.first, x.second);
if(i) {
if(query(actualAns[revranges[i-1].second], ans[x.second])) full(x);
else some(x);
} else {
if(revranges[i+1].second - revranges[i+1].first != 2) { // next one is sorted we can use that
if(query(ans[x.first], actualAns[revranges[i+1].first])) full(x);
else some(x);
} else { // waste three queries because dog problem
int alice = query(ans[x.first], ans[revranges[i+1].first+1]);
int bob = query(ans[x.first + 1], ans[revranges[i+1].first+1]);
int cindy = query(ans[x.first + 2], ans[revranges[i+1].first+1]);
if(alice + bob + cindy == 1) { // this value is D, so we can full the next subarray and
// printf("stupid\n");
some(revranges[i+1]);
if(alice) full(x);
else some(x);
} else {
// printf("idiot\n");
alice = query(ans[x.first], ans[revranges[i+1].first+2]);
bob = query(ans[x.first + 1], ans[revranges[i+1].first+2]);
cindy = query(ans[x.first + 2], ans[revranges[i+1].first+2]);
full(revranges[i+1]);
if(alice) full(x);
else some(x);
}
i++;
}
}
}
}
vector<int> ans2(n);
for(int i = 0; i < n; i++) ans2[actualAns[i]] = i;
// for(auto i : actualAns) cout << i << ' '; cout << '\n';
// for(auto i : ans2) cout << i << ' '; cout << '\n';
return ans2;
}
