#include "xylophone.h"
#include <bits/stdc++.h>
static int A[5000];
void solve(int N) {
int l = 0, r = N-1;
while(true) {
int m = (l + r) / 2;
// std::cout << l << ' ' << r << '\n';
if(query(l+1, m+1) == N-1){
r = m;
}
else if(query(m+2, r+1) == N-1){
l = m+1;
}
else{
break;
}
}
int li = (l+r+1) / 2;
int ri = r;
// std::cout << "----\n";
while(li != ri){
// std::cout << li << ' ' << ri << '\n';
int m = (li + ri) / 2;
if(query(l+1, m+1) == N-1){
ri = m;
}
else{
li = m+1;
}
}
int Max = li;
std::set<int> used;
std::vector<int> B(N);
B[Max] = N;
used.insert(N);
int temp_max = Max;
bool accending = false;
for(int i = Max+1; i < N; i++){
int diff = query(i, i+1);
if(B[i-1] + diff > N || used.count(B[i-1] + diff)){
B[i] = B[i-1] - diff;
used.insert(B[i]);
continue;
}
if(B[i-1] - diff < 1 || used.count(B[i-1] - diff)){
used.insert(B[i]);
B[i] = B[i-1] + diff;
continue;
}
int diff2 = query(i-1, i+1);
if(diff2 == abs(B[i-1] - B[i-2]) || diff2 == diff){
if(B[i-1] > B[i-2]){
B[i] = B[i-1] - diff;
}
else{
B[i] = B[i-1] + diff;
}
used.insert(B[i]);
continue;
}
if(B[i-1] > B[i-2]){
B[i] = B[i-1] + diff;
}
else{
B[i] = B[i-1] - diff;
}
used.insert(B[i]);
}
for(int i = Max-1; i >= 0; i--){
int diff = query(i+1, i+2);
if(B[i+1] + diff > N || used.count(B[i+1] + diff)){
B[i] = B[i+1] - diff;
used.insert(B[i]);
continue;
}
if(B[i+1] - diff < 1 || used.count(B[i+1] - diff)){
B[i] = B[i+1] + diff;
used.insert(B[i]);
continue;
}
int diff2 = query(i+1, i+3);
if(diff2 == abs(B[i+1] - B[i+2]) || diff2 == diff){
if(B[i+1] > B[i+2]){
B[i] = B[i+1] - diff;
}
else{
B[i] = B[i+1] + diff;
}
used.insert(B[i]);
continue;
}
if(B[i+1] > B[i+2]){
B[i] = B[i+1] + diff;
}
else{
B[i] = B[i+1] - diff;
}
used.insert(B[i]);
}
for(int i = 0; i < N; i++){
// std::cout << B[i] << ' ';
answer(i+1, B[i]);
}
// std::cout << '\n';
}
