#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int N = 5e3+1;
int ans[N], n;
bool us[N];
// [i, j, k]
int que(int l, int r) {
return query(min(l, r), max(l, r));
}
int val(int i, int j, int k, int l) {
int p=que(k, i), res=0;
int y=ans[k], a=ans[j];
assert(y != a+l), assert(y != a-l);
if (y > a+l) {
if (p == y-a) res=a+l;
else res=a-l;
} else if (y > a && y < a+l) {
if (p == l) res=a+l;
else res=a-l;
} else if (y < a && y > a-l) {
if (p == l) res=a-l;
else res=a+l;
} else if (y < a-l) {
if (p == a-y) res=a-l;
else res=a+l;
}
assert(1 <= res && res <= n);
assert(!us[res]);
return res;
}
void solve(int np) {
n=np;
int l=1, r=n, x=1;
while (l <= r) {
int m=(l+r)/2;
if (que(1, m) == n-1) r=m-1, x=m;
else l=m+1;
} ans[x]=n;
if (x < n) ans[x+1]=n-que(x, x+1), us[ans[x+1]]=true;
if (x > 1) ans[x-1]=n-que(x-1, x), us[ans[x-1]]=true;
us[n]=true;
for (int i=x+2; i<=n; ++i) {
int l=que(i-1, i);
if (ans[i-1]+l > n || us[ans[i-1]+l]) ans[i]=ans[i-1]-l;
else if (ans[i-1]-l < 1 || us[ans[i-1]-l]) ans[i]=ans[i-1]+l;
else ans[i]=val(i, i-1, i-2, l);
us[ans[i]]=true;
}
for (int i=x-2; i>=1; --i) {
int l=que(i, i+1);
if (ans[i+1]+l > n || us[ans[i+1]+l]) ans[i]=ans[i+1]-l;
else if (ans[i+1]-l < 1 || us[ans[i+1]-l]) ans[i]=ans[i+1]+l;
else ans[i]=val(i, i+1, i+2, l);
us[ans[i]]=true;
}
for (int i=1; i<=n; ++i) {
assert(ans[i] > 0);
answer(i, ans[i]);
}
}
