#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
static int A[5000];
int sv[5010][5010],CC=0;
int myqry(int l,int r){
if(l>r)swap(l,r);
if(l==r)return 0;
if(sv[l][r])return sv[l][r];
assert(++CC<10000);
return sv[l][r]=query(l,r);
}
int ans[5010];
int makesense(int a,int b,int c,int ac){
return ac==max({a,b,c})-min({a,b,c});
}
void solve(int N) {
int l=1,r=N-1,res=0;
while(l<=r){
int mid=l+r>>1;
if(myqry(mid,N)==N-1)
res=mid,l=mid+1;
else r=mid-1;
}
int posof1=res;
ans[posof1]=1;
if(posof1>1)
ans[posof1-1]=myqry(posof1-1,posof1)+1;
ans[posof1+1]=myqry(posof1,posof1+1)+1;
for(int i=posof1-2;i>0;i--){
int k=myqry(i,i+1);
if(ans[i+1]-k<1)
ans[i]=ans[i+1]+k;
else if(ans[i+1]+k>N)
ans[i]=ans[i+1]-k;
else {
int c=query(i,i+2);
if(makesense(ans[i+1]-k,ans[i+1],ans[i+2],c))
ans[i]=ans[i+1]-k;
else ans[i]=ans[i+1]+k;
}
}
for(int i=posof1+2;i<=N;i++){
int k=myqry(i-1,i);
if(ans[i-1]-k<1)
ans[i]=ans[i-1]+k;
else if(ans[i+1]+k>N)
ans[i]=ans[i-1]-k;
else {
int c=query(i-2,i);
if(makesense(ans[i-1]-k,ans[i-1],ans[i-2],c))
ans[i]=ans[i-1]-k;
else ans[i]=ans[i-1]+k;
}
}
for(int i=1;i<=N;i++)
answer(i,ans[i]);
}
