#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
// static int A[5000];
struct range {int l, r, k, x, mx;};
void solve(int n) {
vector<int> ans(n+10, 0);
queue<range> q;
for (int i = n; i >= 2; i--) {
int y = (i-1==1?0:query(1, i-1));
if (y != n-1) {
q.push({1, i, 1, n, 1});
if (i != n) q.push({i, n, 0, n, 1});
ans[i] = n;
break;
}
}
while (!q.empty()) {
auto [l, r, k, x, mx] = q.front(); q.pop();
int dif = query(l, r);
if (k) {
for (int i = l; i < r; i++) {
int y = (i+1==r?0:query(i+1, r));
if (y != dif) {
if (mx) ans[i] = x-dif;
else ans[i] = x+dif;
int m = (l+r)/2;
if (m+1 != r) q.push({m+1, r, k, x, mx});
if (i != m) q.push({i, m, !k, ans[i], !mx});
if (l != i) q.push({l, i, k, ans[i], !mx});
break;
}
}
} else {
for (int i = r; i > l; i--) {
int y = (i-1==l?0:query(l, i-1));
if (y != dif) {
if (mx) ans[i] = x-dif;
else ans[i] = x+dif;
int m = (l+r)/2;
if (i-1 != l) q.push({l, m, k, x, mx});
if (m != i) q.push({m+1, i, !k, ans[i], !mx});
if (i != r) q.push({i, r, k, ans[i], !mx});
break;
}
}
}
}
// for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl;
for (int i = 1; i <= n; i++) answer(i, ans[i]);
}
