#include <bits/stdc++.h>
#include "xylophone.h"
#define pb push_back
#define ll long long
#define vll vector <ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;
void solve(int n){
ll a;
ll l = 1, r = n-1, mid;
while(l <r){
if(l+1 == r){
if(query(r, n) == n-1)l =r;
break;
}
mid = (l+r)/2;
if(query(mid, n) == n-1){
l = mid;
}else r = mid-1;
}a = l;
vll res(n+1); res[a]=1;
vbool ans(n+1); ans[1] = true;
if(a > 1){
ll d = query(a-1, a);
res[a-1] = d+1;
ans[d+1]=true;
}
for(ll i = a-2; i > 0; i--){
ll y = query(i, i+1);
ll z = abs(res[i+1]-res[i+2]);
if(res[i+1]+y > n){
res[i] = res[i+1]-y;
ans[res[i+1]-y] = true;
continue;
}else if(ans[res[i+1]+y]){
res[i] = res[i+1]-y;
ans[res[i+1]-y] = true;
continue;
}
if(res[i+1]-y < 1){
res[i] = res[i+1]+y;
ans[res[i+1]+y] = true;
continue;
}else if(ans[res[i+1]-y]){
res[i] = res[i+1]+y;
ans[res[i+1]+y] = true;
continue;
}
ll x = query(a-2, a);
if(x == y+z){
if(res[i+1] > res[i+2]){
res[i] = res[i+1]+y;
ans[res[i+1]+y] = true;
}else{
res[i] = res[i+1]-y;
ans[res[i+1]-y] = true;
}
}else{
if(res[i+1] > res[i+2]){
res[i] = res[i+1]-y;
ans[res[i+1]-y] = true;
}else{
res[i] = res[i+1]+y;
ans[res[i+1]+y] = true;
}
}
}
res[a+1] = 1 + query(a, a+1);
ans[1 + query(a, a+1)] = true;
for(ll i = a+2; i <= n; i++){
ll y = query(i-1, i);
ll z = abs(res[i-1]-res[i-2]);
if(res[i-1]+y > n){
res[i] = res[i-1]-y;
ans[res[i-1]-y] = true;
continue;
}else if(ans[res[i-1]+y]){
res[i] = res[i-1]-y;
ans[res[i-1]-y] = true;
continue;
}
if(res[i-1]-y < 1){
res[i] = res[i-1]+y;
ans[res[i-1]+y] = true;
continue;
}else if(ans[res[i-1]-y]){
res[i] = res[i-1]+y;
ans[res[i-1]+y] = true;
continue;
}
ll x = query(a, a+2);
if(x == y+z){
if(res[i-1] > res[i-2]){
res[i] = res[i-1]+y;
ans[res[i-1]+y] = true;
}else{
res[i] = res[i-1]-y;
ans[res[i-1]-y] = true;
}
}else{
if(res[i-1] > res[i-2]){
res[i] = res[i-1]-y;
ans[res[i-1]-y] = true;
}else{
res[i] = res[i-1]+y;
ans[res[i-1]+y] = true;
}
}
}
for(ll i = 1; i <= n; i++)answer(i, res[i]);
}
// int main(){
// ios::sync_with_stdio(false); cin.tie(nullptr);
// ll t=1; //cin >> t;
// for(int i = 1; i <= t; i++){
// solve();
// }
// }
