#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=que(i, j), res=0;
if (ans[j]+l > n || us[ans[j]+l]) res=ans[j]-l;
else if (ans[j]-l < 1 || us[ans[j]-l]) res=ans[j]+l;
else {
int p=query(k, i);
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;
}
}
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-query(x, x+1);
if (x > 1) ans[x-1]=n-query(x-1, x);
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);
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);
us[ans[i]]=true;
}
for (int i=1; i<=n; ++i) {
assert(ans[i] > 0);
answer(i, ans[i]);
}
}
