#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll a[5005],used[N],diff[N];
void solve(ll r,ll n){
while(r<n){
ll x=diff[r];
if((a[r]+x<=n&&(!used[a[r]+x]))&&(a[r]-x>=1&&(!used[a[r]-x]))){
ll k=query(r-1,r+1);
if(k==max({a[r]+x,a[r],a[r-1]})-min({a[r]+x,a[r],a[r-1]})){
a[r+1]=a[r]+x;
}else{
a[r+1]=a[r]-x;
}
}else{
if(a[r]+x<=n&&(!used[a[r]+x])){
a[r+1]=a[r]+x;
}else a[r+1]=a[r]-x;
}
r++;
used[a[r]]=1;
}
}void solve1(ll l,ll n){
while(l>1){
ll x=diff[l-1];
if((a[l]+x<=n&&(!used[a[l]+x]))&&(a[l]-x>=1&&(!used[a[l]-x]))){
ll k=query(l-1,l+1);
if(k==max({a[l]+x,a[l],a[l+1]})-min({a[l]+x,a[l],a[l+1]})){
a[l-1]=a[l]+x;
}else{
a[l-1]=a[l]-x;
}
}else{
if(a[l]+x<=n&&(!used[a[l]+x])){
a[l-1]=a[l]+x;
}else a[l-1]=a[l]-x;
}
l--;
used[a[l]]=1;
}
}
void solve(int n) {
for(ll i=1;i<n;i++)diff[i]=query(i,i+1);
ll l=1,r=n;
while(l<r){
ll mid=(r+l)>>1;
if(query(1,mid)==n-1)r=mid;
else l=mid+1;
}
a[l]=n;
solve(l,n);
solve1(l,n);
for(ll i=1;i<=n;i++)answer(i,a[i]);
}
