#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
void solve(int n){
int bl = 1, br = n;
while (bl + 1 < br){
int m = (bl + br) / 2;
if (query(1, m) == (n - 1)){
br = m;
}
else {
bl = m + 1;
}
}
if (query(1, bl) == (n - 1)) br = bl;
int p = br;
vector<int> f(n + 1); f[p] = n;
vector<bool> used(n + 1); used[n] = 1;
if (p > 1){
f[p - 1] = n - query(p - 1, p);
used[f[p - 1]] = 1;
}
if (p < n){
f[p + 1] = n - query(p, p + 1);
used[f[p + 1]] = 1;
}
for (int i = p - 2; i > 0; i--){
int u = query(i, i + 1);
if (f[i + 1] <= u || used[f[i + 1] - u]){
f[i] = f[i + 1] + u;
used[f[i]] = 1;
continue;
}
if ((f[i + 1] + u) > n || used[f[i + 1] + u]){
f[i] = f[i + 1] - u;
used[f[i]] = 1;
continue;
}
int v = query(i, i + 2);
if (f[i + 1] > f[i + 2]){
f[i] = (v == (f[i + 1] + u - f[i + 2])) ? (f[i + 1] + u) : (f[i + 1] - u);
}
else {
f[i] = (v == (f[i + 2] - f[i + 1] + u)) ? (f[i + 1] - u) : (f[i + 1] + u);
}
used[f[i]] = 1;
}
for (int i = p + 2; i <= n; i++){
int u = query(i - 1, i);
if (f[i - 1] <= u || used[f[i - 1] - u]){
f[i] = f[i - 1] + u;
used[f[i]] = 1;
continue;
}
if ((f[i - 1] + u) > n || used[f[i - 1] + u]){
f[i] = f[i - 1] - u;
used[f[i]] = 1;
continue;
}
int v = query(i - 2, i);
if (f[i - 2] > f[i - 1]){
f[i] = (v == (f[i - 2] - f[i - 1] + u)) ? (f[i - 1] - u) : (f[i - 1] + u);
}
else {
f[i] = (v == (f[i - 1] + u - f[i - 2])) ? (f[i - 1] + u) : (f[i - 1] - u);
}
used[f[i]] = 1;
}
for (int i = 1; i <= n; i++){
answer(i, f[i]);
}
}
