#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
int asked[5001][5001];
int ask(int l, int r){
if(asked[l][r]!=-1)
return asked[l][r];
asked[l][r]=query(l,r);
return asked[l][r];
}
void solve(int N) {
int arr[N+1];
int i,j;
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
asked[i][j]=-1;
int l=1,r=N;
while(l<r){
int mid=(l+r)/2;
int x=ask(1,mid);
if(x==N-1)
r=mid-1;
else
l=mid+1;
}
int found;
int x=ask(1,l);
if(x==N-1)
found=l;
else
found=l+1;
//cout<<found<<endl;
arr[found]=N;
if(found>1){
int x=ask(found-1,found);
arr[found-1]=N-x;
}
if(found<N){
int x=ask(found,found+1);
arr[found+1]=N-x;
}
for(i=found-2;i>=1;i--){
int x2=ask(i,i+1);
int x3=ask(i,i+2);
int p1=arr[i+1]-x2;
int p2=arr[i+1]+x2;
if(max({p1,arr[i+1],arr[i+2]})-min({p1,arr[i+1],arr[i+2]})==x3)
arr[i]=p1;
else
arr[i]=p2;
}
for(i=found+2;i<=N;i++){
int x2=ask(i-1,i);
int x3=ask(i-2,i);
int p1=arr[i-1]-x2;
int p2=arr[i-1]+x2;
if(max({p1,arr[i-1],arr[i-2]})-min({p1,arr[i-1],arr[i-2]})==x3)
arr[i]=p1;
else
arr[i]=p2;
}
for(i=1;i<=N;i++)
answer(i,arr[i]);
}
