#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int bio [5010]; int l [5010];
int moze (int x, int n){
if (x>n || x<1) return 0;
if (bio[x]) return 0;
return 1;
}
int moze2 (int x, int y, int diff1, int diff2){
int z1=y+diff1, z2=y-diff1;
if (max (abs(x-y), max(abs (x-z1), abs (y-z1)))==diff2) return z1;
return z2;
}
void solve (int n){
int lo=1; int hi=n;
while (hi-lo>1){
//cout << lo << " " << hi;
int mid=(lo+hi)/2;
int x=query (mid, n);
if (x==n-1) lo=mid;
else hi=mid-1;
}
if (hi!=lo){
if (query (hi, n)==n-1) lo++;
}
//cout << lo;
bio [1]=1; l[lo]=1;
for (int i=lo+1; i<n+1; i++){
int x=query (i-1, i);
if (moze (l[i-1]+x, n) && moze (l[i-1]-x, n)){
int y=query (i-2, i);
l[i]=moze2 (l[i-2], l[i-1], x, y); bio [moze2 (l[i-2], l[i-1], x, y)]=1;
}
else{
if (moze(l[i-1]+x, n)){
l[i]=l[i-1]+x; bio [l[i-1]+x]=1;
}
else{
l[i]=l[i-1]-x; bio [l[i-1]-x]=1;
}
}
}
for (int i=lo-1; i>0; i--){
int x=query (i, i+1);
if (moze (l[i+1]+x, n) && moze (l[i+1]-x, n)){
int y=query (i, i+2);
l[i]=moze2 (l[i+2], l[i+1], x, y); bio [moze2 (l[i+2], l[i+1], x, y)]=1;
}
else{
if (moze(l[i+1]+x, n)){
l[i]=l[i+1]+x; bio [l[i+1]+x]=1;
}
else{
l[i]=l[i+1]-x; bio [l[i+1]-x]=1;
}
}
}
for (int i=1; i<n+1; i++) answer (i, l[i]);
}
