#include <bits/stdc++.h>
using namespace std;
#include "xylophone.h"
void solve(int N){
int pos = 1;
{
int l = 1, r = N;
while (r - l > 1){
int mid = (l + r) >> 1;
if (query(mid, N) == N-1) l = mid;
else r = mid-1;
}
if (l != r){
if (query(r, N) == N-1) pos = r;
else pos = l;
}
else pos = l;
}
vector<int> res(N + 1, 0);
set<int> alr;
res[pos] = 1; alr.insert(1);
for (int i = pos + 1; i <= N; i++){
int diff = query(i - 1, i);
vector<int> opts;
for (int sign: {-1, 1}){
int cand = res[i - 1] + sign * diff;
if (1 <= cand && cand <= N && !alr.count(cand)) opts.push_back(cand);
}
if ((int)opts.size() == 1){
res[i] = opts[0];
alr.insert(res[i]);
}
else{
int d2 = query(i - 2, i);
for (int j = 0; j < (int)opts.size(); j++){
if (d2 == max({res[i - 2], res[i - 1], opts[j]}) - min({res[i - 2], res[i - 1], opts[j]})){
res[i] = opts[j];
alr.insert(res[i]);
break;
}
}
}
}
for (int i = pos - 1; i >= 1; i--){
int diff = query(i, i + 1);
vector<int> opts;
for (int sign: {-1, 1}){
int cand = res[i + 1] + sign * diff;
if (1 <= cand && cand <= N && !alr.count(cand)) opts.push_back(cand);
}
if ((int)opts.size() == 1){
res[i] = opts[0];
alr.insert(res[i]);
}
else{
int d2 = query(i, i + 2);
for (int j = 0; j < (int)opts.size(); j++){
if (d2 == max({res[i + 2], res[i + 1], opts[j]}) - min({res[i + 2], res[i + 1], opts[j]})){
res[i] = opts[j];
alr.insert(res[i]);
break;
}
}
}
}
for (int i = 1; i <= N; i++) answer(i, res[i]);
}
