#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005];
bool vis[5005];
void solve(int N) {
int l = 1,r = N;
while(l < r){
int m = (l + r)/2;
if(query(1,m) != N-1){
l = m+1;
}
else r = m;
}
A[l] = N;
vis[N] = 1;
answer(l,N);
for(int i = l-1; i>=1; i--){
int dif = query(i,i+1);
if(A[i+1] + dif > N || vis[A[i+1] + dif]){
A[i] = A[i+1] - dif;
vis[A[i]] = 1;
answer(i,A[i]);
continue;
}
if(A[i+1] - dif < 1 || vis[A[i+1] - dif]){
A[i] = A[i+1] + dif;
vis[A[i]] = 1;
answer(i,A[i]);
continue;
}
for(int j = i + 1;j<=l;j++){
if(A[j] > A[i+1] + dif){
int val = query(i,j);
if(val == A[j] - (A[i+1] - dif)){
A[i] = (A[i+1] - dif);
}
else A[i] = (A[i+1] + dif);
break;
}
if(A[j] < A[i+1] - dif){
int val = query(i,j);
if(val == (A[i+1] + dif) - A[j]){
A[i] = (A[i+1] + dif);
}
else A[i] = (A[i+1] - dif);
break;
}
}
vis[A[i]] = 1;
answer(i,A[i]);
}
for(int i = l+1; i<=N; i++){
int dif = query(i-1,i);
if(A[i-1] + dif > N || vis[A[i-1] + dif]){
A[i] = A[i-1] - dif;
vis[A[i]] = 1;
answer(i,A[i]);
continue;
}
if(A[i-1] - dif < 1 || vis[A[i-1] - dif]){
A[i] = A[i-1] + dif;
vis[A[i]] = 1;
answer(i,A[i]);
continue;
}
for(int j = i -1;j>=l;j--){
if(A[j] > A[i-1] + dif){
int val = query(j,i);
if(val == A[j] - (A[i-1] - dif)){
A[i] = (A[i-1] - dif);
}
else A[i] = (A[i-1] + dif);
break;
}
if(A[j] < A[i-1] - dif){
int val = query(j,i);
if(val == (A[i-1] + dif) - A[j]){
A[i] = (A[i-1] + dif);
}
else A[i] = (A[i-1] - dif);
break;
}
}
vis[A[i]] = 1;
answer(i,A[i]);
}
}
