#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int NM = 5000;
int p[NM+5], q[NM+5];
bool used[NM+5];
void process(int p[NM+5], int i, int x, int y){
if (p[i-2] < p[i-1]){
if (p[i-1]-x < p[i-2]){
if (y == x){
p[i] = p[i-1]-x;
}
else{
p[i] = p[i-1]+x;
}
}
else{
if (y == p[i-1]-p[i-2]){
p[i] = p[i-1]-x;
}
else{
p[i] = p[i-1]+x;
}
}
}
else{
if (p[i-1]+x > p[i-2]){
if (y == x){
p[i] = p[i-1]+x;
}
else{
p[i] = p[i-1]-x;
}
}
else{
if (y == p[i-2]-p[i-1]){
p[i] = p[i-1]+x;
}
else{
p[i] = p[i-1]-x;
}
}
}
}
void modify(int N, int p[NM+5]){
int mn = p[1];
for (int i = 2; i <= N; i++)
mn = min(mn, p[i]);
for (int i = 1; i <= N; i++)
p[i] += 1-mn;
}
bool ok(int N, int p[NM+5]){
memset(used, 0, sizeof(used));
int a, b;
for (int i = 1; i <= N; i++){
if (used[p[i]]) return 0;
used[p[i]] = 1;
if (p[i] == 1) a = i;
if (p[i] == N) b = i;
}
return a < b;
}
void output(int N, int p[NM+5]){
for (int i = 1; i <= N; i++)
answer(i, p[i]);
}
void solve(int N){
p[1] = 0;
p[2] = query(1, 2);
q[2] = -p[2];
for (int i = 3; i <= N; i++){
int x = query(i-1, i), y = query(i-2, i);
process(p, i, x, y);
process(q, i, x, y);
}
modify(N, p);
modify(N, q);
if (!ok(N, q)){
output(N, p);
return;
}
if (!ok(N, p)){
output(N, q);
return;
}
for (int i = 1; i <= N; i++){
int mxp = p[i], mnp = p[i], mxq = q[i], mnq = q[i];
for (int j = i+1; j <= N; j++){
mxp = max(mxp, p[j]);
mnp = min(mnp, p[j]);
mxq = max(mxq, q[j]);
mnq = min(mnq, q[j]);
if ((mxp-mnp) != (mxq-mnq)){
if (query(i, j) == mxq-mnq){
output(N, q);
return;
}
else{
output(N, p);
return;
}
}
}
}
}
