#include <iostream>
#include <xylophone.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF -1
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
initrand;
int N;
map<int, bool> seen;
/*int query(int s, int t){
cout<<"Query asked: "<<s<<" "<<t<<endl;
int ans;
cin>>ans;
return ans;
}
void answer(int i, int a){
cout<<"Answer for index "<<i<<" is "<<a<<endl;
}*/
int findOne(int n){
int l = 2;
int u = n;
int tr = n-1;
while(l<=u){
int m = mid(l, u);
if(query(m, n) < (n-1)){
tr = min(tr, m-1);
u = m-1;
}
else l = m+1;
}
return tr;
}
int diff(int a, int b, int c){
return max(a, max(b, c)) - min(a, min(b, c));
}
int findPrev(int i, int prev, int prev1){
int temp = query(i, i+1);
int poss1 = prev+temp;
int poss2 = prev-temp;
if(seen[poss1] || poss1>N) return poss2;
if(seen[poss2] || poss2<1) return poss1;
temp = query(i, i+2);
if(temp == diff(prev, prev1, poss1)) return poss1;
return poss2;
}
int findNext(int i, int prev, int prev1){
int temp = query(i-1, i);
int poss1 = prev+temp;
int poss2 = prev-temp;
if(seen[poss1] || poss1>N) return poss2;
if(seen[poss2] || poss2<1) return poss1;
temp = query(i-2, i);
if(temp == diff(prev, prev1, poss1)) return poss1;
return poss2;
}
void solve(int n){
N = n;
int arr[n+1];
int oind = findOne(n);
arr[oind] = 1;
seen[1] = true;
arr[oind + 1] = 0;
for(int j = oind-1;j>=1;j--){
arr[j] = findPrev(j, arr[j+1], arr[j+2]);
seen[arr[j]] = true;
}
for(int j = oind+1;j<=n;j++){
arr[j] = findNext(j, arr[j-1], ((j-2)>=1)?arr[j-2]:0);
seen[arr[j]] = true;
}
for(int i = 1;i<=n;i++) answer(i, arr[i]);
}
