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

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1005;

int a[MAXN], b[MAXN];

bool cmp(int x, int y) { return Query(x, y); }

void Sort(int l, int r) {
	if(l == r) return ; int mid = l + r >> 1;
	Sort(l, mid); Sort(mid + 1, r);
	int i = l, j = mid + 1, k = l;
	while(i <= mid || j <= r) 
		if(i <= mid && (j > r || cmp(a[j], a[i]))) b[k++] = a[i++];
		else b[k++] = a[j++];
	rep(i, l, r) a[i] = b[i];
}

int get(int lmt) {
	vc<vc<int> > w(lmt + 1, vc<int> (lmt + 1, 0)); vc<int> g(lmt + 1), o(lmt + 1), p(lmt + 1, 0);
	rep(i, 1, lmt) rep(j, i + 1, lmt) {
		w[i][j] = w[j][i] = cmp(a[i], a[j]);
		if(w[i][j]) ++g[i];
		else ++g[j];
	}
	rep(i, 1, lmt) {
		o[i] = i;
		rep(j, 1, lmt) if(j != i && w[i][j]) p[i] = j;
	}
	
	sort(o.begin() + 1, o.end(), [&](int x, int y) {
		return g[x] != g[y] ? g[x] < g[y] : g[p[x]] < g[p[y]];
	});
	return o[1];
}

vc<int> Solve(int n) {
	rep(i, 1, n) a[i] = i - 1;
	Sort(1, n);
	
	int pos = get(min(n, 10));
	reverse(a + 1, a + 1 + pos);
	for(int i = pos + 1, j = pos; i <= n; i++) 
		if(j == n || cmp(a[j], a[i])) {
			reverse(a + j + 1, a + i + 1);
			j = i;
		} 
	
	vc<int> ans, p(n + 1, 0);
	rep(i, 1, n) p[a[i]] = i - 1;
	rep(i, 1, n) ans.pb(p[i - 1]);
	return ans;
}