#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
void solve(int N);
int query(int s, int t);
void answer(int i, int a);
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int A[maxn];
int n;
bool used[maxn];
int A1[maxn];
int A2[maxn];
void Set(int i, int a) {
answer(i,a);
used[a]=true;
A[i]=a;
}
void ask1(int i) {
if (A1[i]) return;
A1[i] = query(i,i+1);
}
void ask2(int i) {
assert(i+2<=n);
if (A2[i]) return;
A2[i] = query(i,i+2);
}
bool isUsed(int x) {
if (x<1 || x>n) return true;
return used[x];
}
void solve(int _n) {
n=_n;
int in = -1;
// find in
{
int lo = 1;
int hi = n;
while (hi-lo>1) {
int mid = (lo+hi)/2;
if (query(1,mid)==n-1) {
hi = mid;
} else {
lo = mid;
}
}
in = hi;
}
auto bruteL = [&](int i) {
//watch(i);
assert(i+2<=n);
assert(A[i+1]); assert(A[i+2]);
ask1(i);
ask1(i+1);
ask2(i);
vector<int> op;
op.push_back(A[i+1]-A1[i]);
op.push_back(A[i+1]+A1[i]);
for (int x: op) {
if (x<1 || x>n) continue;
A[i]=x;
bool ok = true;
int gap=max(abs(A[i]-A[i+1]),abs(A[i+1]-A[i+2]));
if (gap > A2[i]) {
ok = false;
}
if (A1[i] < A2[i] && A1[i+1]==A2[i]) {
// we have to be in the middle
// 2 3 1 or 2 1 3
int lo = min(A[i+1],A[i+2]);
int hi = max(A[i+1],A[i+2]);
if (!(lo<A[i] && A[i]<hi)) {
ok = false;
}
} else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
// 3 1 2 or 1 3 2
if (A[i+1]<A[i+2]) {
if (!(A[i]>max(A[i+1],A[i+2]))) {
ok = false;
}
} else if (A[i+1]>A[i+2]) {
if (!(A[i]<min(A[i+1],A[i+2]))) {
ok = false;
}
} else {
assert(false);
}
} else if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
// 1 2 3 or 3 2 1
if (A[i+1]<A[i+2]) {
if (!(A[i]<A[i+1])) {
ok = false;
}
}
if (A[i+1]>A[i+2]) {
if (!(A[i]>A[i+1])) {
ok = false;
}
}
} else {
assert(false);
}
if (ok) break;
}
};
auto bruteR = [&](int i) {
// i, i+1, (i+2)
ask1(i);
ask2(i);
ask1(i+1);
assert(A[i]);
assert(A[i+1]);
vector<int> op;
op.push_back(A[i+1]-A1[i+1]);
op.push_back(A[i+1]+A1[i+1]);
for (int x: op) {
if (x<1 || x>n) continue;
if (isUsed(x)) continue;
A[i+2] = x;
bool ok = true;
if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
// 1 2 3 or 3 2 1
if (A[i]<A[i+1]) {
if (!(A[i+1]<A[i+2])) {
ok = false;
}
} else if (A[i]>A[i+1]) {
if (!(A[i+1]>A[i+2])) {
ok = false;
}
} else {
assert(false);
}
} else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
// 1 3 2 or 3 1 2
int lo = min(A[i],A[i+1]);
int hi = max(A[i],A[i+1]);
if (!(lo<=A[i+2] && A[i+2]<=hi)) {
ok = false;
}
} else if (A1[i+1]==A2[i] && A1[i]<A2[i]) {
int lo = min(A[i],A[i+1]);
int hi = max(A[i],A[i+1]);
if (!(lo<=A[i+2] && A[i+2]<=hi)) {
ok = false;
}
if (A[i]>A[i+1]) {
if (!(A[i+2]>A[i])) {
ok = false;
}
} else if (A[i]<A[i+1]) {
if (!(A[i+2]<A[i])) {
ok = false;
}
} else {
assert(false);
}
} else {
assert(false);
}
if (ok) {
break;
}
}
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1
};
Set(in,n);
// go left
for (int i=in-1; i>=1; i--) {
ask1(i);
int dif=A1[i];
if (isUsed(A[i+1]-dif)) {
Set(i, A[i+1]+dif);
} else if (isUsed(A[i+1]+dif)) {
Set(i, A[i+1]-dif);
} else {
assert(i+2<=n);
bruteL(i);
assert(A[i]);
}
}
// cout<<"A: ";
// for (int i=1; i<=n; i++) {
// cout<<A[i]<<" ";
// }
// cout<<endl;
// cout<<"go right"<<endl;
// go right
for (int i=in; i<n; i++) {
ask1(i);
int dif=A1[i];
if (isUsed(A[i]-dif)) {
Set(i+1, A[i]+dif);
} else if (isUsed(A[i+1]+dif)) {
Set(i+1, A[i]-dif);
} else {
assert(i-1>=1);
bruteR(i-1);
//assert(A[i+1]);
}
}
for (int i=1; i<=n; i++) {
if (!isUsed(i)) {
Set(n,i);
break;
}
}
}
