#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
vector<int> a(N + 1, 0);
vector<bool> used(N + 1, false);
// 1. Find position of 1 using binary search
int low = 1, high = N, pos1 = 1;
while (low <= high) {
int mid = (low + high) / 2;
if (mid == N) break; // Avoid query(N, N) if unnecessary
if (query(mid, N) == N - 1) {
pos1 = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
auto determine = [&](int cur, int prev, int pprev) {
int d1 = query(min(cur, prev), max(cur, prev));
int c1 = a[prev] + d1;
int c2 = a[prev] - d1;
// Validation against bounds and used numbers
if (c1 < 1 || c1 > N || used[c1]) return c2;
if (c2 < 1 || c2 > N || used[c2]) return c1;
// Tie-breaker using query(i-2, i)
int d2 = query(min(cur, pprev), max(cur, pprev));
if (max({a[prev], a[pprev], c1}) - min({a[prev], a[pprev], c1}) == d2) {
return c1;
}
return c2;
};
// Initialize 1
a[pos1] = 1;
used[1] = true;
// 2. Solve Right
if (pos1 < N) {
a[pos1 + 1] = 1 + query(pos1, pos1 + 1);
used[a[pos1 + 1]] = true;
for (int i = pos1 + 2; i <= N; i++) {
a[i] = determine(i, i - 1, i - 2);
used[a[i]] = true;
}
}
// 3. Solve Left
if (pos1 > 1) {
a[pos1 - 1] = 1 + query(pos1 - 1, pos1);
used[a[pos1 - 1]] = true;
for (int i = pos1 - 2; i >= 1; i--) {
a[i] = determine(i, i + 1, i + 2);
used[a[i]] = true;
}
}
for (int i = 1; i <= N; i++) {
answer(i, a[i]);
}
}
