#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
bool example_variable;
} // namespace
void finish(vector<int>& vec, vector<int>& res, int start, int lowindex) {
cerr << "FINISH " << start << " " << lowindex << "\n";
if(start == vec.size())
return;
int index = start;
while(Query(vec[lowindex], vec[index])) {
index++;
}
cerr << "\t" << index << "\n";
for(int i = start, j = index; i < index + 1; i++, j--) {
res[i] = vec[j];
}
finish(vec, res, index + 1, start);
}
void resolve(vector<int>& vec, vector<int>& res, int start) {
if(vec.size() - start <= 6) {
int n = vec.size() - start;
cerr << "brute" << n << "\n";
vector<int> winc(vec.size());
for(int i = start; i < vec.size(); i++) {
for(int j = i + 1; j < vec.size(); j++) {
if(Query(vec[i], vec[j]))
winc[i]++;
else
winc[j]++;
}
}
cerr << "WINC\n";
for(int i = start; i < vec.size(); i++)
cerr << winc[i] << " ";
cerr << "\n";
vector<int> sw;
vector<int> sl;
for(int i = start; i < vec.size(); i++) {
if(winc[i] == 1) {
sw.push_back(vec[i]);
}
else if(winc[i] == n - 2) {
sl.push_back(vec[i]);
}
else {
res[res.size() - winc[i] - 1] = vec[i];
}
}
cerr << "swl " << sw[0] << " " << sw[1] << " "<< sl[0] << " "<< sl[1] << "\n";
if(vec.size() - start == 4) {
if(Query(sw[0], sl[0]) || Query(sw[0], sl[1])) {
res[start + 2] = sw[0];
res[start + 3] = sw[1];
}
else {
res[start + 2] = sw[1];
res[start + 3] = sw[0];
}
if(Query(sl[0], sw[0]) && Query(sl[0], sw[1])) {
res[start] = sl[0];
res[start + 1] = sl[1];
}
else {
res[start] = sl[1];
res[start + 1] = sl[0];
}
}
else if(vec.size() - start >= 5) {
if(Query(res[start + 2], sl[0])) {
res[start] = sl[1];
res[start + 1] = sl[0];
}
else {
res[start] = sl[0];
res[start + 1] = sl[1];
}
if(Query(res[res.size() - 3], sw[0])) {
res[res.size() - 2] = sw[1];
res[res.size() - 1] = sw[0];
}
else {
res[res.size() - 2] = sw[0];
res[res.size() - 1] = sw[1];
}
}
else {
cerr << "ERR\n";
}
cerr << "BRUTERES\n";
for(int a : res)
cerr << a << " ";
cerr << "\n";
return;
}
if(Query(vec[start], vec[start + 2])) {
cerr << "finish\n";
int index = start + 3;
while(index < vec.size() && Query(vec[start], vec[index])) {
index++;
}
if(index == vec.size()) {
cerr << "OVERFLOW\n";
cerr << "OWF RES\n";
for(int a : res)
cerr << a << " ";
cerr << "\n";
cerr << start << " " << index << "\n";
index--;
//res[start] = vec[start];
//res[start + 1] = vec[start];
for(int i = start + 2, j = index; i < vec.size(); i++, j--) {
res[i] = vec[j];
}
cerr << "OWF RES\n";
for(int a : res)
cerr << a << " ";
cerr << "\n";
return;
}
cerr << "s " << start << " ix " << index << "\n";
cerr << vec[start + 1] << " " << vec[index] << "\n";
if(Query(vec[start + 1], vec[index])) {
cerr << "MAX 2\n";
res[start] = vec[start + 1];
res[start + 1] = vec[start];
for(int i = start + 2, j = index; i <= index; i++, j--) {
res[i] = vec[j];
}
finish(vec, res, index + 1, start + 2);
//resolve(vec, res, index + 1);
}
else {
cerr << "MAX 1\n";
res[start] = vec[start];
for(int i = start + 1, j = index; i <= index; i++, j--) {
res[i] = vec[j];
}
finish(vec, res, index + 1, start + 1);
//resolve(vec, res, index + 1);
}
//resolve(vec, res, index + 1);
return;
}
bool q1 = Query(vec[start + 3], vec[start]);
bool q2 = Query(vec[start + 3], vec[start + 1]);
bool q3 = Query(vec[start + 3], vec[start + 2]);
cerr << "Q" << q1 << " " << q2 << " " << q3 << "\n";
if((q1 && q2) || (q1 && q3) || (q2 && q3)) {
cerr << "4 ^\n";
int index = start + 4;
while(Query(vec[index], vec[start + 1])) {
index++;
}
index--;
cerr << start << " " << index << "\n";
for(int i = index, j = start; i >= start; i--, j++) {
res[i] = vec[j];
}
resolve(vec, res, index + 1);
return;
}
cerr << "recursion\n";
resolve(vec, res, start + 3);
cerr << "rec\n";
int a = vec[start];
int b = vec[start + 1];
int c = vec[start + 2];
cerr << "\t" << start << " " << res[start + 3] << " " << a << " " << b << " " << c << " "<< Query(vec[start], vec[start + 1])<< " " << Query(vec[start + 1], vec[start + 2]) << " " << Query(vec[start + 2], vec[start]) << "\n";
for(int a : res)
cerr << a << " ";
cerr << "\n";
if(!Query(a, res[start + 3])) {
cerr << "1st\n";
res[start] = c;
res[start + 1] = b;
res[start + 2] = a;
}
else if(!Query(b, res[start + 3])) {
cerr << "2nd\n";
res[start] = a;
res[start + 1] = c;
res[start + 2] = b;
}
else if(!Query(c, res[start + 3])) {
cerr << "3rd\n";
res[start] = b;
res[start + 1] = a;
res[start + 2] = c;
}
else{
cerr << "err\n";
}
}
vector<int> Solve(int N) {
vector<vector<int>> vec(N, vector<int>());
for(int i = 0; i < N; i++) {
vec[i].push_back(i);
}
while(vec.size() != 1) {
cerr << "VEC:\n";
for(vector<int> v : vec) {
for(int i : v)
cerr << i << " ";
cerr << "\n";
}
cerr << "\n";
vector<vector<int>> newvec;
for(int i = 0; i < vec.size(); i += 2) {
vector<int> vec1 = vec[i];
vector<int> vec2 = vec.size() > i + 1 ? vec[i+1] : vector<int>();
vector<int> res;
int a = 0;
int b = 0;
for(; a < vec1.size() && b < vec2.size(); ) {
cerr << vec1[a] << " " << vec2[b] << "\n";
if(Query(vec1[a], vec2[b])) {
res.push_back(vec1[a]);
a++;
}
else {
res.push_back(vec2[b]);
b++;
}
}
for(int j = a; j < vec1.size(); j++) {
res.push_back(vec1[j]);
}
for(int j = b; j < vec2.size(); j++) {
res.push_back(vec2[j]);
}
newvec.push_back(res);
}
vec = newvec;
}
cerr << "VEC FINAL:\n";
for(vector<int> v : vec) {
for(int i : v)
cerr << i << " ";
cerr << "\n";
}
cerr << "\n";
vector<int> res(N);
cerr << "--------------------\n";
resolve(vec[0], res, 0);
cerr << "RES: ";
for(int a : res)
cerr << a << " ";
cerr << "\n";
vector<int> ret(N);
for(int i = 0; i < N; i++) {
ret[res[N - i - 1]] = i;
}
cerr << "RET: ";
for(int a : ret)
cerr << a << " ";
return ret;
}
