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