#include "art.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(), (x).end()
#define mp(x) iota(all((x)), 1)
int n;
/*
where[x] vector of length N+1, stores the position of collection x in the permutation (-1 if we dont know)
who[pos] vector of length N+1, stores which collection is currently at position pos in the permutation (-1 if we dont know)
*/
vi invert(vi &where) {
vi who(n+1, -1);
for (int i = 1; i <= n; i++) {
if (where[i] != -1) who[where[i]] = i;
}
return who;
}
struct State {
vi where, who;
set<int> unused;
};
vi make_perm(State state) {
vi rt(n, -1);
for (int i = 1; i <= n; i++) {
if (state.where[i] == -1) continue;
rt[state.where[i] - 1] = i;
}
int cur_pos = 0;
for (auto &el : state.unused) {
while (rt[cur_pos] != -1) cur_pos++;
rt[cur_pos] = el;
}
return rt;
}
int best_at(State state, int pos) {
auto ns = state;
int best = INT_MAX, best_node = -1;
for (int i = 1; i <= n; i++) {
if (!state.unused.count(i)) continue;
ns.unused.erase(i);
ns.where[i] = pos;
ns.who = invert(ns.where);
int res = publish(make_perm(ns));
ns.where[i] = -1;
ns.who = invert(ns.where);
ns.unused.insert(i);
if (res < best) {
best = res;
best_node = i;
}
}
return best_node;
}
void solve(int N) {
n = N;
// find the best node for each index and recompute state
State state;
for (int i = 1; i <= n; i++) state.unused.insert(i);
state.where.assign(n+1,-1);
state.who.assign(n+1,-1);
for (int i = 1; i <= n; i++) {
int best = best_at(state, i);
state.unused.erase(best);
state.where[best] = i;
state.who = invert(state.where);
}
vector<int> vorder(n);
for (int i = 1; i <= n; i++) {
vorder[i-1] = state.who[i];
}
answer(vorder);
}
