#include "xylophone.h"
static int A[5000];
void solve(int n) {
int l = 1, r = n;
while(l != r){
int m = (l + r) / 2;
if(m == 1){
l = 2;
break;
}
int res = query(1, m);
if(res == n-1) r = m;
else l = m+1;
}
int ans[n+1], ans2[n+1];
for(int i = 0; i <= n; i++) ans2[i] = -1;
ans[l] = n;
// cout << ans[l] << endl;
ans2[n] = 1;
if(l != n) ans[l+1] = n - query(l, l+1), ans2[ans[l+1]] = 1;
// cout << l << " " << ans[l] << " " << ans[l+1]<<endl;
for(int i = l+2; i <= n; i++){
int hmmm = query(i-1,i);
if(ans[i-1] + hmmm > n - 1){
ans[i] = ans[i-1] - hmmm;
ans2[ans[i-1]-hmmm] = 1;
continue;
}
if(ans[i-1] - hmmm < 1){
ans[i] = ans[i-1] + hmmm;
ans2[ans[i-1]+hmmm] = 1;
continue;
}
if(ans2[ans[i-1] + hmmm] != -1){
ans[i] = ans[i-1] - hmmm;
ans2[ans[i-1]-hmmm] = 1;
continue;
}
if(ans2[ans[i-1] - hmmm] != -1){
ans[i] = ans[i-1] + hmmm;
ans2[ans[i-1]+hmmm] = 1;
continue;
}
int of = query(i-2, i);
if(ans[i-2]<ans[i-1]){
if(of == (ans[i-1]-ans[i-2] + hmmm)) ans[i] = ans[i-1] + hmmm, ans2[ans[i-1] + hmmm] = 1;
else ans[i] = ans[i-1] - hmmm, ans2[ans[i-1] - hmmm] = 1;
}
else{
if(of == (ans[i-2]-ans[i-1] + hmmm)) ans[i] = ans[i-1] - hmmm, ans2[ans[i-1] - hmmm] = 1;
else ans[i] = ans[i-1] + hmmm, ans2[ans[i-1] + hmmm] = 1;
}
}
if(l != 1) ans[l-1] = n - query(l-1, l), ans2[ans[l-1]] = l-1;
for(int i = l-2; i > 0; i--){
int hmmm = query(i,i+1);
if(ans[i+1] + hmmm > n-1){
ans[i] = ans[i+1] - hmmm;
ans2[ans[i+1]-hmmm] = 1;
continue;
}
if(ans[i+1] - hmmm < 1){
ans[i] = ans[i+1] + hmmm;
ans2[ans[i+1]+hmmm] = 1;
continue;
}
if(ans2[ans[i+1] + hmmm] != -1){
ans[i] = ans[i+1] - hmmm;
ans2[ans[i+1]-hmmm] = 1;
continue;
}
if(ans2[ans[i+1] - hmmm] != -1){
ans[i] = ans[i+1] + hmmm;
ans2[ans[i+1]+hmmm] = 1;
continue;
}
int of = query(i, i+2);
if(ans[i+2]<ans[i+1]){
if(of == (ans[i+1]-ans[i+2] + hmmm)) ans[i] = ans[i+1] + hmmm, ans2[ans[i+1] + hmmm] = 1;
else ans[i] = ans[i+1] - hmmm, ans2[ans[i+1] - hmmm] = 1;
}
else{
if(of == (ans[i+2]-ans[i+1] + hmmm)) ans[i] = ans[i+1] - hmmm, ans2[ans[i+1] - hmmm] = 1;
else ans[i] = ans[i+1] + hmmm, ans2[ans[i+1] + hmmm] = 1;
}
}
for(int i = 1; i <= n; i++) answer(i, ans[i]);
}
