#include "xylophone.h"
static int A[5010];
static bool used[5010]={0};
int n;
inline void Set(int i, int x) {
A[i]=x;
used[x]=1;
}
inline bool Poss(int x) {
return 1<=x&&x<=n&&!used[x];
}
void solve(int N) {
n=N;
int lo=1, hi=N, x, y;
while(lo<hi) {
int mid=(lo+hi+1)/2;
x=query(mid,N);
if(x==N-1) lo=mid;
else hi=mid-1;
}
Set(lo,1);
int i;
if(lo+1<=N) {
x=query(lo,lo+1);
Set(lo+1,x+1);
}
if(lo-1>=1) {
x=query(lo-1,lo);
Set(lo-1,x+1);
}
for(i=lo+2;i<=N;i++) {
x=query(i-1,i);
if(!Poss(A[i-1]+x)) {
Set(i,A[i-1]-x);
} else if(!Poss(A[i-1]-x)) {
Set(i,A[i-1]+x);
} else {
if(A[i-2]>A[i-1]) {
y=query(i-2,i);
if(y==A[i-2]-A[i-1]+x) {
Set(i,A[i-1]-x);
} else {
Set(i,A[i-1]+x);
}
} else {
y=query(i-2,i);
if(y==A[i-1]-A[i-2]+x) {
Set(i,A[i-1]+x);
} else {
Set(i,A[i-1]-x);
}
}
}
}
for(i=lo-2;i>=1;i--) {
x=query(i,i+1);
if(!Poss(A[i+1]+x)) {
Set(i,A[i+1]-x);
} else if(!Poss(A[i+1]-x)) {
Set(i,A[i+1]+x);
} else {
if(A[i+2]>A[i+1]) {
y=query(i,i+2);
if(y==A[i+2]-A[i+1]+x) {
Set(i,A[i+1]-x);
} else {
Set(i,A[i+1]+x);
}
} else {
y=query(i,i+2);
if(y==A[i+1]-A[i+2]+x) {
Set(i,A[i+1]+x);
} else {
Set(i,A[i+1]-x);
}
}
}
}
for(i=1;i<=N;i++) answer(i,A[i]);
}
