#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> m;
int qq(int L, int R) {
if (m[{L, R}] != 0) {
return m[{L, R}];
}
return m[{L, R}] = query(L, R);
}
void solve(int n) {
int l = 1, r = n, idx = r;
while(l <= r) {
int mid = (l + r) / 2;
if (qq(mid, n) == n-1) {
idx = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// cout << idx << "\n";
vector<bool> seen(n+5, false);
vector<int> an(n+5, -1);
an[idx] = 1;
if (idx != 1) {
int val = qq(idx-1, idx);
an[idx-1] = val + 1;
seen[val] = true;
}
for(int i = idx-2; i >= 1; i--) {
int val = qq(i, idx);
if (!seen[val]) {
an[i] = val + 1;
seen[val] = true;
} else {
an[i] = an[i+1] - qq(i, i+1);
}
}
if (idx != n) {
int val = qq(idx, idx+1);
an[idx+1] = val + 1;
seen[val] = true;
}
for(int i = idx+2; i <= n; i++) {
int val = qq(idx, i);
if (!seen[val]) {
an[i] = val + 1;
seen[val] = true;
} else {
an[i] = an[i-1] - qq(i-1, i);
}
}
for(int i = 1; i <= n; i++) {
answer(i, an[i]);
}
}
