#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const int N=5050,inf=1e9;
int a[N];
void solve(int n){
int l=1,r=n,idx=0;
while(l<=r){
int mid=l+r>>1;
if(query(mid,n)==n-1){l=mid+1;idx=mid;}
else r=mid-1;
}
bool was[n+10]={false};
a[idx]=1;was[1]=true;
int d[n+10];
for(int i=1;i<n;i++) d[i]=query(i,i+1);
if(idx+1<=n) a[idx+1]=1+d[idx],was[a[idx+1]]=true;
if(idx-1>=1) a[idx-1]=a[idx]+d[idx-1],was[a[idx-1]]=true;
for(int i=idx+2;i<=n;i++){
if(!(1<=a[i-1]+d[i-1]&&a[i-1]+d[i-1]<=n)||was[a[i-1]+d[i-1]]) a[i]=a[i-1]-d[i-1];
else if(!(1<=a[i-1]-d[i-1]&&a[i-1]-d[i-1]<=n)||was[a[i-1]-d[i-1]]) a[i]=a[i-1]+d[i-1];
else{
int x=query(i-2,i);
if(x==d[i-1]||x==d[i-2]){
if(a[i-2]>a[i-1]) a[i]=a[i-1]+d[i-1];
else a[i]=a[i-1]-d[i-1];
}
else{
if(a[i-2]<a[i-1]) a[i]=a[i-1]+d[i-1];
else a[i]=a[i-1]-d[i-1];
}
}
was[a[i]]=true;
}
for(int i=idx-2;i>=1;i--){
if(!(1<=a[i+1]+d[i]&&a[i+1]+d[i]<=n)||was[a[i+1]+d[i]]) a[i]=a[i+1]-d[i];
else if(!(1<=a[i+1]-d[i]&&a[i+1]-d[i]<=n)||was[a[i+1]-d[i]]) a[i]=a[i+1]+d[i];
else{
int x=query(i,i+2);
if(x==d[i+1]||x==d[i]){
if(a[i+2]>a[i+1]) a[i]=a[i+1]+d[i];
else a[i]=a[i+1]-d[i];
}
else{
if(a[i+2]<a[i+1]) a[i]=a[i+1]+d[i];
else a[i]=a[i+1]-d[i];
}
}
was[a[i]]=true;
}
for(int i=1;i<=n;i++) answer(i,a[i]);
}
