#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll
#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2
int ans[5007];
int used[5007];
void solve(int n)
{
int L=1,R=n;
while (R-L>1)
{
int M=(L+R)>>1;
if (query(M,n)!=n-1) R=M;
else L=M;
}
int _1_at=L;
ans[_1_at]=1;
if (_1_at!=n)
ans[_1_at+1]=query(_1_at,_1_at+1)+1;
if (_1_at!=1)
ans[_1_at-1]=query(_1_at-1,_1_at)+1;
for (int i=_1_at+1;i<=n-1;i++)
{
int tmp1=query(i,i+1);
if (ans[i]-tmp1<1||used[ans[i]-tmp1])
{
ans[i+1]=ans[i]+tmp1;
used[ans[i+1]]=1;
continue;
}
if (ans[i]+tmp1>n||used[ans[i]+tmp1])
{
ans[i+1]=ans[i]-tmp1;
used[ans[i+1]]=1;
continue;
}
int tmp2=query(i-1,i+1);
if (tmp2==tmp1+abs(ans[i]-ans[i-1]))
{
if (ans[i]>ans[i-1]) ans[i+1]=ans[i-1]+tmp2;
else ans[i+1]=ans[i-1]-tmp2;
}
else
{
if (ans[i]>ans[i-1]) ans[i+1]=ans[i]-tmp1;
else ans[i+1]=ans[i]+tmp1;
}
used[ans[i+1]]=1;
}
for (int i=_1_at;i<=n;i++) used[ans[i]]=1;
for (int i=_1_at-1;i>=2;i--)
{
int tmp1=query(i-1,i);
if (ans[i]-tmp1<1||used[ans[i]-tmp1])
{
ans[i-1]=ans[i]+tmp1;
used[ans[i-1]]=1;
continue;
}
if (ans[i]+tmp1>n||used[ans[i]+tmp1])
{
ans[i-1]=ans[i]-tmp1;
used[ans[i-1]]=1;
continue;
}
int tmp2=query(i-1,i+1);
if (tmp2==tmp1+abs(ans[i]-ans[i+1]))
{
if (ans[i]>ans[i+1]) ans[i-1]=ans[i+1]+tmp2;
else ans[i-1]=ans[i+1]-tmp2;
}
else
{
if (ans[i]>ans[i+1]) ans[i-1]=ans[i]-tmp1;
else ans[i-1]=ans[i]+tmp1;
}
used[ans[i-1]]=1;
}
for (int i=1;i<=n;i++) answer(i,ans[i]);
}
