#include "xylophone.h"
#include <iostream>
#include <vector>
using namespace std;
int a[5005];
vector<int> g[5005];
void solve(int N) {
int ma = 0, l = 0;
for (int i = 2; i <= N; i++) {
int h = query(1, i);
ma = max(ma, h);
g[h].push_back(i);
}
if (g[ma].size() == 2) {
int h = g[ma][0], k = g[ma][1];
if (h < k) a[h] = 1, a[k] = N, l = h;
else a[h] = N, a[k] = 1, l = k;
}
else {
int h = g[ma][0];
int d = N - ma, e = ma + 1;
int t = g[d - 1][0], tt = g[d - 1][1];
int k = query(t, h), kk = query(tt, h);
if (k == N - 1) {
if (t > h) swap(t, h);
a[t] = 1;
a[h] = N;
a[1] = d;
l = t;
}
else if (kk == N - 1) {
if (tt > h) swap(tt, h);
a[tt] = 1;
a[h] = N;
a[1] = d;
l = tt;
}
else {
t = g[N - e][0], tt = g[N - e][1];
k = query(t, h), kk = query(tt, h);
if (k == N - 1) {
if (t < h) swap(t, h);
a[h] = 1;
a[t] = N;
a[1] = e;
l = h;
}
else if (kk == N - 1) {
if (tt < h) swap(tt, h);
a[h] = 1;
a[tt] = N;
a[1] = e;
l = h;
}
}
}
for (int i = 1; i <= N; i++) {
if (a[i] == 0) {
int h = query(i, l);
a[i] = h + 1;
}
}
for (int i = 1; i <= N; i++) answer(i, a[i]);
}
