#include "xylophone.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 *1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
static int A[5000];
int cur[N], dif[N];
bool was[N];
void solve(int n) {
int l = 1, r = n, rx;
while(r - l > 1){
int mid = (r + l) / 2;
if(query(1, mid) == n - 1) r = mid;
else l = mid;
}
rx = r;
cur[rx] = n;
was[n] = true;
for(int i = rx + 1; i <= n; i++){
int rs = query(i - 1, i);
int fr = cur[i - 1] - rs, sc = cur[i - 1] + rs;
if(sc > n || was[sc]){
cur[i] = fr;
was[fr] = true;
continue;
}
if(fr < 1 || was[fr]){
cur[i] = sc;
was[sc] = true;
continue;
}
int rs2 = query(i - 2, i);
if(rs2 == abs(cur[i - 1] - cur[i - 2])){
if(cur[i - 2] > cur[i - 1]) cur[i] = sc;
else cur[i] = fr;
} else{
if(rs2 == rs){
if(cur[i - 2] > cur[i - 1]) cur[i] = sc;
else cur[i] = fr;
} else{
if(cur[i - 2] > cur[i - 1]) cur[i] = fr;
else cur[i] = sc;
}
}
was[cur[i]] = true;
}
for(int i = rx - 1; i >= 1; i--){
int rs = query(i, i + 1);
int fr = cur[i + 1] - rs, sc = cur[i + 1] + rs;
if(sc > n || was[sc]){
cur[i] = fr;
was[fr] = true;
continue;
}
if(fr < 1 || was[fr]){
cur[i] = sc;
was[sc] = true;
continue;
}
int rs2 = query(i, i + 2);
if(rs2 == abs(cur[i + 1] - cur[i + 2])){
if(cur[i + 2] > cur[i + 1]) cur[i] = sc;
else cur[i] = fr;
} else{
if(rs2 == rs){
if(cur[i + 2] > cur[i + 1]) cur[i] = sc;
else cur[i] = fr;
} else{
if(cur[i + 2] > cur[i + 1]) cur[i] = fr;
else cur[i] = sc;
}
}
was[cur[i]] = true;
}
for(int i = 1; i <= n; i++) {
answer(i, cur[i]);
}
}
