#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
vector<int> ans(N + 1, 0);
int LJ = 1, HJ = N;
while (LJ < HJ) {
int mid = (LJ + HJ + 1) / 2;
int q = query(mid, N);
if (q == N - 1) {
LJ = mid;
}
else {
HJ = mid - 1;
}
}
int pos1 = LJ;
ans[pos1] = 1;
int current_max = 1;
int idx_max = pos1;
for (int i = pos1 + 1; i <= N; ++i) {
int q = query(pos1, i);
if (q > current_max - 1) {
ans[i] = q + 1;
current_max = ans[i];
idx_max = i;
}
else {
int s = min(idx_max, i);
int t = max(idx_max, i);
int d = query(s, t);
ans[i] = current_max - d;
}
}
current_max = 1;
idx_max = pos1;
for (int i = pos1 - 1; i >= 1; --i) {
int q = query(i, pos1);
if (q > current_max - 1) {
ans[i] = q + 1;
current_max = ans[i];
idx_max = i;
}
else {
int s = min(idx_max, i);
int t = max(idx_max, i);
int d = query(s, t);
ans[i] = current_max - d;
}
}
for (int i = 1; i <= N; ++i) {
answer(i, ans[i]);
}
}
