#include "xylophone.h"
#include <vector>
using namespace std;
void solve(int n) {
vector<int> ans(n+1);
vector<bool> used(n+1);
int l = 1, r = n;
int first = 0;
while (l <= r){
int mid = (l + r) / 2;
if (query(mid, n) == n-1){
first = mid;
l = mid + 1;
} else r = mid - 1;
}
ans[first] = 1;
used[1] = true;
for (int i = first - 1; i > 0; --i){
int k = query(i, i+1);
int x = ans[i+1] + k;
int y = ans[i+1] - k;
if (y < 1 || used[y]) ans[i] = x, used[x] = true;
else if (x > n || used[x]) ans[i] = y, used[y] = true;
else{
int a = query(i, i+2);
int mn = min(ans[i+1], ans[i+2]);
int mx = max(ans[i+1], ans[i+2]);
if (a == mx - mn && x > mn && x < mx) ans[i] = x, used[x] = true;
else if (a == mx - mn) ans[i] = y, used[y] = true;
else if (a == max(mx, x) - min(mn, x)) ans[i] = x, used[x] = true;
else ans[i] = y, used[y] = true;
}
}
for (int i = first + 1; i <= n; ++i){
int k = query(i-1, i);
int x = ans[i-1] + k;
int y = ans[i-1] - k;
if (y < 1 || used[y]) ans[i] = x, used[x] = true;
else if (x > n || used[x]) ans[i] = y, used[y] = true;
else{
int a = query(i-2, i);
int mn = min(ans[i-1], ans[i-2]);
int mx = max(ans[i-1], ans[i-2]);
if (a == mx - mn && x > mn && x < mx) ans[i] = x, used[x] = true;
else if (a == mx - mn) ans[i] = y, used[y] = true;
else if (a == max(mx, x) - min(mn, x)) ans[i] = x, used[x] = true;
else ans[i] = y, used[y] = true;
}
}
for (int i = 1; i <= n; ++i) {
answer(i, ans[i]);
}
}
