#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int a[5005];
map<int, int> fr;
int findN()
{
int st=2, dr=n, mij, last=-1;
while(st <= dr)
{
mij = (st+dr)/2;
//cout<<1<<' '<<mij<<'\n';
if(query(1, mij) == n-1)
{
last=mij;
dr=mij-1;
}
else
st=mij+1;
}
return last;
}
bool bad(int x)
{
if(x > n)
return true;
if(x <= 0)
return true;
if(fr[x])
return true;
return false;
}
void solve(int N)
{
n=N;
int p = findN();
if(p == -1)
exit(1);
a[p] = n;
fr[n] = 1;
int mini=n, minP = p;
for(int i=p-1;i>=1;i--)
{
int dif = query(i, i+1);
int x1 = a[i+1] - dif;
int x2 = a[i+1] + dif;
if(bad(x1))
a[i]=x2;
else if(bad(x2))
a[i]=x1;
else
{
int nQ = query(i, minP);
if(nQ == x2 - mini)
a[i]=x2;
else
a[i]=x1;
}
mini=min(mini, a[i]);
if(mini == a[i])
minP = i;
fr[ a[i] ] =1;
}
mini=n, minP = p;
for(int i=p+1;i<=n;i++)
{
int dif = query(i-1, i);
int x1 = a[i-1] - dif;
int x2 = a[i-1] + dif;
if(bad(x1))
a[i]=x2;
else if(bad(x2))
a[i]=x1;
else
{
int nQ = query(minP, i);
if(nQ == x2 - mini)
a[i]=x2;
else
a[i]=x1;
}
mini=min(mini, a[i]);
if(mini == a[i])
minP = i;
fr[ a[i] ] =1;
}
/*
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
*/
for(int i=1;i<=n;i++)
answer(i, a[i]);
}
