#include <bits/stdc++.h>
#include <xylophone.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n;
int a[maxN];
bool counted[maxN];
void solve(int N){
n = N;
int l = 1, r = n - 1;
while (l <= r){
int m = (l + r) / 2;
if (query(m, n) == n - 1) l = m + 1;
else r = m - 1;
}
a[r] = 1;
answer(r, a[r]);
a[r + 1] = a[r] + query(r, r + 1);
answer(r + 1, a[r + 1]);
for (int i = r + 2; i <= n; ++i){
int x = a[i - 2];
int y = a[i - 1];
int d2 = query(i - 1, i);
if (a[i - 1] + d2 > n || counted[a[i - 1] + d2]){
a[i] = a[i - 1] - d2;
answer(i, a[i]);
continue;
}
if (a[i - 1] - d2 < 1 || counted[a[i - 1] - d2]){
a[i] = a[i - 1] + d2;
answer(i, a[i]);
continue;
}
int d1 = query(i - 2, i);
int c = a[i - 1] - d2;
int minn = min(min(c, a[i - 1]), a[i - 2]);
int maxx = max(max(c, a[i - 1]), a[i - 2]);
if (query(i - 2, i) == maxx - minn){
a[i] = c;
answer(i, c);
}
else{
a[i] = a[i - 1] + d2;
answer(i, a[i]);
}
counted[a[i]] = 1;
}
if (r > 1){
a[r - 1] = a[r] + query(r - 1, r);
answer(r - 1, a[r - 1]);
}
for (int i = r - 2; i >= n; --i){
int x = a[i + 2];
int y = a[i + 1];
int d2 = query(i, i + 1);
if (a[i + 1] + d2 > n || counted[a[i + 1] + d2]){
a[i] = a[i + 1] - d2;
answer(i, a[i]);
continue;
}
if (a[i + 1] - d2 < 1 || counted[a[i + 1] - d2]){
a[i] = a[i + 1] + d2;
answer(i, a[i]);
continue;
}
int d1 = query(i, i + 2);
int c = a[i + 1] - d2;
int minn = min(min(c, a[i + 1]), a[i + 2]);
int maxx = max(max(c, a[i + 1]), a[i + 2]);
if (query(i + 2, i) == maxx - minn){
a[i] = c;
answer(i, c);
}
else{
a[i] = a[i + 1] + d2;
answer(i, a[i]);
}
counted[a[i]] = 1;
}
}
