#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
int p = 1;
int r = N;
while(p<r) {
int m = (p+r+1)/2;
if(query(m, N)==N-1) p = m;
else r = m-1;
}
set<int>revealed;
revealed.insert(1);
int ans[N+1];
ans[p] = 1;
if(p!=1) {
ans[p-1] = query(p-1, p);
}
for(int i=p-2; i>0; --i) {
int x = query(i, i+1);
if(revealed.count(ans[i+1]+x)) {
ans[i] = ans[i+1]-x;
} else if(revealed.count(ans[i+1]-x)) {
ans[i] = ans[i+1]+x;
} else {
//grey
int y = query(i, i+2);
if(ans[i+1]>ans[i+2]) {
if(y==ans[i+1]-ans[i+2]+x) {
ans[i] = ans[i+1]+x;
} else {
ans[i] = ans[i+1]-x;
}
} else {
if(y==ans[i+2]-ans[i+1]+x) {
ans[i] = ans[i+1]-x;
} else {
ans[i] = ans[i+1]+x;
}
}
}
revealed.insert(ans[i]);
}
ans[p+1] = query(p, p+1)+1;
for(int i=p+2; i<=N; ++i) {
int x = query(i-1, i);
if(revealed.count(ans[i-1]+x)) {
ans[i] = ans[i-1]-x;
} else if(revealed.count(ans[i-1]-x)) {
ans[i] = ans[i-1]+x;
} else {
//grey
int y = query(i-2, i);
if(ans[i-1]>ans[i-2]) {
if(y==ans[i-1]-ans[i-2]+x) {
ans[i] = ans[i-1]+x;
} else {
ans[i] = ans[i-1]-x;
}
} else {
if(y==ans[i-2]-ans[i-1]+x) {
ans[i] = ans[i-1]-x;
} else {
ans[i] = ans[i-1]+x;
}
}
}
revealed.insert(ans[i]);
}
for(int i=1; i<=N; ++i) {
answer(i, ans[i]);
}
}
