#include "monster.h"
#include <bits/stdc++.h>

#define debug(...) fprintf (stderr, __VA_ARGS__)

void msort(std :: vector<int> &p) {
	if (p.size() == 1) return ;
	std :: vector<int> L, R;
	int mid = p.size() >> 1; -- mid;
	for (int i = 0; i <= mid; i ++) L.push_back (p[i]);
	for (int i = mid + 1; i < (int) p.size(); i ++) R.push_back (p[i]);
	msort (L); msort (R);
	p.clear();
	int i = 0, j = 0;
	while (i < L.size() || j < R.size()) {
		if (i == L.size()) p.push_back (R[j]), j ++;
		else if (j == R.size()) p.push_back (L[i]), i ++;
		else if (Query (L[i], R[j])) p.push_back (R[j]), j ++;
		else p.push_back (L[i]), i ++;
	}
}

inline std :: vector<int> get(std :: vector<int> p) {
	std :: vector<int> ans = p;
	for (int i = 0; i < (int) p.size(); i ++) ans[p[i]] = i;
	return ans;
}

std :: vector<int> brute_force(int n) {
	std :: vector<int> p(n), cnt(n);
	std :: map<int, std :: map<int, int> > f;
	std :: iota (p.begin(), p.end(), 0);
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++) if (i != j) if (f[p[i]][p[j]] = Query (p[i], p[j])) ++ cnt[p[i]];
	std :: sort (p.begin(), p.end(), [&] (int x, int y) -> bool {
		if (cnt[x] != cnt[y]) return cnt[x] < cnt[y];
		return f[x][y];
	} );

	return p;
}

std :: vector<int> Solve(int n) {
	std :: vector<int> p(n);
	std :: iota (p.begin(), p.end(), 0);
	
	if (n <= 200) {
		return get (brute_force(n) );
	}

	msort (p);
	const int m = 30;
	std :: vector<int> cnt(n);
	for (int i = 0; i < m; i ++)
		for (int j = 0; j < m; j ++) if (i != j) if (Query (p[i], p[j])) ++ cnt[p[i]];
	int m1 = -1, m2 = -1;
	for (int i = 0; i < m; i ++) {
		if (cnt[p[i]] == 0) std :: swap (m1, m2), m2 = i;
	}

	if ( Query (m1, m2)) ; else std :: swap (m1, m2);

	int now = m1;
	std :: reverse (p.begin(), p.begin() + now + 1);
	now ++;
	for (int i = now; i < n; i ++) {
		if (Query (p[now - 1], p[i])) {
			std :: reverse (p.begin() + now, p.begin() + i + 1);
			now = i + 1;
		}
	}

	std :: reverse (p.begin() + now, p.end());

	return get (p);
}