#include <cstdio>
#include <cstdlib>
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int num[5006];
void solve(int menge) {
int be = 1 , en = menge , comp , cmp;
while(query(be , en) == menge - 1){
be++;
}
be--;
while(query(be , en) == menge - 1){
en--;
}
en++;
num[be] = 1;
num[en] = menge;
cout << be << ' ' << en << "\n";
if(be > 1){
num[be - 1] = 1 + query(be - 1 , be);
}
num[be + 1] = 1 + query(be , be + 1);
if(en < menge){
num[en + 1] = menge - query(en , en + 1);
}
num[en - 1] = menge - query(en - 1 , en);
for(int i = be - 2 ; i > 0 ; i--){
if(num[i] != 0){
continue;
}
// cout << num[i] << "\n";
cmp = query(i , i + 1);
comp = query(i , i + 2);
if(comp == cmp + abs(num[i + 1] - num[i + 2]) ){
num[i] = num[i + 1] + (cmp * ( (num[i + 1] - num[i + 2]) / abs(num[i + 1] - num[i + 2]) ) );
}
else{
num[i] = num[i + 1] + (-1 * cmp * ( (num[i + 1] - num[i + 2]) / abs(num[i + 1] - num[i + 2]) ) );
}
}
for(int i = be + 2 ; i <= menge ; i++){
if(num[i] != 0){
continue;
}
cmp = query(i - 1 , i);
comp = query(i - 2, i);
if(comp == cmp + abs(num[i - 1] - num[i - 2]) ){
num[i] = num[i - 1] + (cmp * ( (num[i - 1] - num[i - 2]) / abs(num[i - 1] - num[i - 2]) ) );
}
else{
num[i] = num[i - 1] + (-1 * cmp * ( (num[i - 1] - num[i - 2]) / abs(num[i - 1] - num[i - 2]) ) );
}
}
// cout << "ja\n";
for(int i = 1; i <= menge ; i++){
answer(i , num[i]);
}
}
