#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
set<int> used;
void solve(int N) {
int pos=N;
int l=0,r=N-1;
while(l<=r){
int med=(l+r)>>1;
if(query(med+1,N)!=(N-1))
r=med-1;
else l=med+1,pos=med;
}
used.insert(1);
A[pos]=1;
answer(pos+1,1);
for (int i = pos-1; i >= 0; i--)
{
int d=query(i+1,i+2);//i-1
int a=A[i+1]+d,b=A[i+1]-d;
if((a<=0)||(a>N)||used.find(a)!=used.end()){A[i]=b,used.insert(b),answer(i+1,b);continue;}
if((b<=0)||(b>N)||used.find(b)!=used.end()){A[i]=a,used.insert(a),answer(i+1,a);continue;}
int h=query(i+1,i+3),val;
if(h!=(abs(A[i+1]-A[i+2])+d)){
if(A[i+1]<A[i+2])val=a;
else val=b;
}
else{
if(A[i+1]<A[i+2])val=b;
else val=a;
}
A[i]=val;
used.insert(val);
answer(i+1,val);
}
for (int i = pos+1; i < N; i++)
{
int d=query(i,i+1);//i-1
int a=A[i-1]+d,b=A[i-1]-d;
if((a<=0)||(a>N)||used.find(a)!=used.end()){A[i]=b,used.insert(b),answer(i+1,b);continue;}
if((b<=0)||(b>N)||used.find(b)!=used.end()){A[i]=a,used.insert(a),answer(i+1,a);continue;}
int h=query(i-1,i+1),val;
if(h!=(abs(A[i-2]-A[i-1])+d)){
if(A[i-2]<A[i-1])val=b;
else val=a;
}
else{
if(A[i-2]<A[i-1])val=a;
else val=b;
}
A[i]=val;
used.insert(val);
answer(i+1,val);
}
}
