#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;
if (p > 1) f[p - 1] = n - query(p - 1, p);
if (p < n) f[p + 1] = n - query(p, p + 1);
for (int i = p - 2; i > 0; i--){
int v = query(i, i + 2), u = query(i, i + 1);
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);
}
}
for (int i = p + 2; i <= n; i++){
int v = query(i - 2, i), u = query(i - 1, 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);
}
}
for (int i = 1; i <= n; i++){
answer(i, f[i]);
}
}
