#include "xylophone.h"
static int A[5000];
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
/*typedef pair<int,int> pii;
#define fi first
#define se second*/
void solve(int n) {
int l=1,h=n;
while(l<h-1){
int m=(l+h)/2;
//debug(m)
int q=query(m,n);
//debug(q)
if(q<n-1)h=m;
else l=m;
}
int a[n+1];
int mi=l;
//debug(mi)
a[mi]=1;
set<int> s={1};
if(mi>1){a[mi-1]=query(mi-1,mi)+1;s.insert(a[mi-1]);}
a[mi+1]=query(mi,mi+1)+1;
s.insert(a[mi+1]);
for(int i=mi-2;i>0;i--){
//debug(1)
int q1=query(i,i+1);
int c1=a[i+1]+q1;
int c2=a[i+1]-q1;
if(s.find(c1)!=s.end()){
s.insert(c2);
a[i]=c2;
continue;
}else if(s.find(c2)!=s.end()){
s.insert(c1);
a[i]=c1;
continue;
}
int q2=query(i,i+2);
if(q1+abs(a[i+1]-a[i+2])==q2){//sorted order
if(a[i+2]>a[i+1])a[i]=c2;//desc
else a[i]=c1;
}else{
if(a[i+2]>a[i+1])a[i]=c1;
else a[i]=c2;
}
s.insert(a[i]);
}
for(int i=mi+2;i<=n;i++){
//debug(2)
int q1=query(i-1,i);
int c1=a[i-1]+q1;
int c2=a[i-1]-q1;
if(s.find(c1)!=s.end()){
s.insert(c2);
a[i]=c2;
continue;
}else if(s.find(c2)!=s.end()){
s.insert(c1);
a[i]=c1;
continue;
}
int q2=query(i-2,i);
if(q1+abs(a[i-1]-a[i-2])==q2){
if(a[i-2]<a[i-1])a[i]=c1;//asc
else a[i]=c2;
}else{
if(a[i-2]<a[i-1])a[i]=c2;
else a[i]=c1;
}
s.insert(a[i]);
}
for(int i=1;i<=n;i++){
//cerr<<a[i]<<' ';
answer(i,a[i]);
}
}
