#include "xylophone.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define bit(mask, i) ((mask >> i) & 1)
#define el '\n'
#define F first
#define S second
template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};
const int N = 5e3 + 5;
int a[N];
bool ok[N];
void solve(n) {
int l = 1, r = n, L = -1, R = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(1, mid) == n - 1) {
R = mid;
r = mid - 1;
} else l = mid + 1;
}
l = 1, r = R - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(mid, R) == n - 1) {
L = mid;
l = mid + 1;
} else r = mid - 1;
}
ok[1] = ok[n] = 1;
a[L] = 1, a[R] = n;
if (L > 1) {
int v = 1 + query(L - 1, L);
a[L - 1] = v; ok[v] = 1;
}
if (L < n && L + 1 != R) {
int v = 1 + query(L, L + 1);
a[L + 1] = v; ok[v] = 1;
}
if (R > 1 && a[R - 1] == 0) {
int v = n - query(R - 1, R);
a[R - 1] = v; ok[v] = 1;
}
if (R < n) {
int v = n - query(R, R + 1);
a[R + 1] = v; ok[v] = 1;
}
for (int i = L - 2; i >= 1; --i) {
int diff = query(i, i + 1);
if (a[i + 1] + diff > n || ok[a[i + 1] + diff]) {
a[i] = a[i + 1] - diff;
ok[a[i]] = 1;
continue;
}
if (a[i + 1] - diff < 1 || ok[a[i + 1] - diff]) {
a[i] = a[i + 1] + diff;
ok[a[i]] = 1;
continue;
}
int diff2 = query(i, i + 2);
if (abs(a[i + 1] - a[i + 2]) == diff2) {
a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] + diff : a[i + 1] - diff);
ok[a[i]] = 1;
}
else if (diff + abs(a[i + 1] - a[i + 2]) == diff2) {
a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] - diff : a[i + 1] + diff);
ok[a[i]] = 1;
}
else {
int v = a[i + 1] - diff, c = 0;
if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
v = a[i + 1] + diff;
if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
if (c != 1) return cout << c, void();
assert(c == 1);
}
}
for (int i = R - 2; i > L + 1; --i) {
int diff = query(i, i + 1);
if (a[i + 1] + diff > n || ok[a[i + 1] + diff]) {
a[i] = a[i + 1] - diff;
ok[a[i]] = 1;
continue;
}
if (a[i + 1] - diff < 1 || ok[a[i + 1] - diff]) {
a[i] = a[i + 1] + diff;
ok[a[i]] = 1;
continue;
}
int diff2 = query(i, i + 2);
if (abs(a[i + 1] - a[i + 2]) == diff2) {
a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] + diff : a[i + 1] - diff);
ok[a[i]] = 1;
}
else if (diff + abs(a[i + 1] - a[i + 2]) == diff2) {
a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] - diff : a[i + 1] + diff);
ok[a[i]] = 1;
}
else {
int v = a[i + 1] - diff, c = 0;
if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
v = a[i + 1] + diff;
if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
assert(c == 1);
}
}
for (int i = R + 2; i <= n; ++i) {
int diff = query(i - 1, i);
if (a[i - 1] + diff > n || ok[a[i - 1] + diff]) {
a[i] = a[i - 1] - diff;
ok[a[i]] = 1;
continue;
}
if (a[i - 1] - diff < 1 || ok[a[i - 1] - diff]) {
a[i] = a[i - 1] + diff;
ok[a[i]] = 1;
continue;
}
int diff2 = query(i - 2, i);
if (abs(a[i - 2] - a[i - 1]) == diff2) {
a[i] = (a[i - 1] < a[i - 2] ? a[i - 1] + diff : a[i - 1] - diff);
ok[a[i]] = 1;
}
else if (diff + abs(a[i - 2] - a[i - 1]) == diff2) {
a[i] = (a[i - 1] < a[i - 2] ? a[i - 1] - diff : a[i - 1] + diff);
ok[a[i]] = 1;
}
else {
int v = a[i - 1] - diff, c = 0;
if (max({v, a[i - 1], a[i - 2]}) - min({v, a[i - 1], a[i - 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
v = a[i - 1] + diff;
if (max({v, a[i - 1], a[i - 2]}) - min({v, a[i - 1], a[i - 2]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
assert(c == 1);
}
}
for (int i = 1; i <= n; ++i)
answer(i, a[i]);
}
