#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int n) {
int l = 0, r = n;
while (l + 1 < r) {
int m = (l + r) / 2;
if (query(1, m) == n - 1) {
r = m;
} else {
l = m;
}
}
vector<int> a(n + 1);
a[r] = n;
int mx = 0, pos = 0;
for (int i = r + 1; i <= n; i++) {
int ret = query(r, i);
if (ret != mx) {
mx = ret;
a[i] = n - mx;
pos = i;
} else {
a[i] = a[pos] + query(pos, i);
}
}
mx = 0, pos = 0;
for (int i = r - 1; i >= 1; i--) {
int ret = query(i, r);
if (ret != mx) {
mx = ret;
a[i] = n - mx;
pos = i;
} else {
a[i] = a[pos] + query(i, pos);
}
}
for (int i = 1; i <= n; i++) {
answer(i, a[i]);
}
}
