#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
int value = query(1, N);
int L = 1, hi = N;
while (L < hi) {
int mid = L + (hi - L + 1) / 2;
if (query(mid, N) == value) L = mid;
else hi = mid - 1;
}
vector<int> ans(N+1, -1);
set<int> avail; for (int i = 2; i <= N; i++) avail.insert(i);
vector<int> indices; for (int i = L; i <= N; i++) indices.push_back(i);
for (int i = L-1; i >= 1; i--) indices.push_back(i);
for (int i : indices) {
if (i == L) ans[i] = 1;
else if (i == L+1) ans[i] = 1 + query(L, i);
else if (i == L-1) ans[i] = 1 + query(i, L);
else {
int dx = i > L ? query(i-1, i) : query(i, i+1);
int p1 = i > L ? i-1 : i+1, p2 = i > L ? i-2 : i+2;
int a = ans[p1] + dx, b = ans[p1] - dx;
int x = ans[p2], y = ans[p1];
// y < a < x, y < x < a, x < y < a
// x < b < y, b < y < x, b < x < y
if (!avail.count(a)) ans[i] = b;
else if (!avail.count(b)) ans[i] = a;
else {
int dy = i > L ? query(i-2, i) : query(i, i+2);
if (y < a && a < x && dy == x-y) ans[i] = a;
else if (y < x && x < a && dy == a-y) ans[i] = a;
else if (x < y && y < a && dy == a-x) ans[i] = a;
else if (x < b && b < y && dy == y-x) ans[i] = b;
else if (b < y && y < x && dy == x-b) ans[i] = b;
else if (b < x && x < y && dy == y-b) ans[i] = b;
}
}
avail.erase(ans[i]);
}
for(int i = 1; i <= N; i++) answer(i, ans[i]);
}
