#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
bool seen[5001];
int ans[5001];
void solve(int n) {
int lo = 1, hi = n;
for (int k = 13; k--;) {
if (hi - (1 << k) >= lo and query(lo, hi - (1 << k)) == n - 1) hi -= 1 << k;
if (lo + (1 << k) <= hi and query(lo + (1 << k), hi) == n - 1) lo += 1 << k;
}
auto upd = [&] (int i, int v) {
answer(i, ans[i] = v);
seen[v] = true;
};
upd(lo, 1);
upd(hi, n);
auto can = [&] (int i) { return i >= 1 and i <= n and not seen[i]; };
auto left = [&] (int i) {
int d = query(i, i + 1);
if (can(ans[i + 1] - d) and can(ans[i + 1] + d)) {
if (max(ans[i + 1], ans[i + 2]) - min(ans[i + 1] - d, ans[i + 2]) == query(i, i + 2)) upd(i, ans[i + 1] - d);
else upd(i, ans[i + 1] + d);
} else if (can(ans[i + 1] - d)) upd(i, ans[i + 1] - d);
else upd(i, ans[i + 1] + d);
};
auto right = [&] (int i) {
int d = query(i - 1, i);
if (can(ans[i - 1] - d) and can(ans[i - 1] + d)) {
if (max(ans[i - 1], ans[i - 2]) - min(ans[i - 1] - d, ans[i - 2]) == query(i - 2, i)) upd(i, ans[i - 1] - d);
else upd(i, ans[i - 1] + d);
} else if (can(ans[i - 1] - d)) upd(i, ans[i - 1] - d);
else upd(i, ans[i - 1] + d);
};
if (lo > 1) upd(lo - 1, 1 + query(lo - 1, lo));
for (int i = lo - 1; --i >= 1;) left(i);
if (lo + 1 < hi) upd(lo + 1, 1 + query(lo, lo + 1));
for (int i = lo + 1; ++i < hi - 1;) right(i);
if (hi - 1 > lo) upd(hi - 1, n - query(hi - 1, hi));
if (hi < n) upd(hi + 1, n - query(hi, hi + 1));
for (int i = hi + 1; ++i <= n;) right(i);
}
