#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int d[5008][3];
int a[5008];
int pos[5008];
bool check(int n) {
fill(pos + 1, pos + n + 1, 0);
for (int i = 1; i <= n; ++i)
if (a[i] <= 0 || a[i] > n) return 0;
else pos[a[i]] = i;
for (int i = 1; i <= n; ++i) if (!pos[i]) return 0;
return pos[1] < pos[n];
}
void deduce(int n) {
for (int i = 3; i <= n; ++i) {
if (a[i - 2] > a[i - 1]) {
if (a[i - 2] - a[i - 1] + d[i][1] == d[i][2]) a[i] = a[i - 1] - d[i][1];
else a[i] = a[i - 1] + d[i][1];
}
else {
if (a[i - 1] - a[i - 2] + d[i][1] == d[i][2]) a[i] = a[i - 1] + d[i][1];
else a[i] = a[i - 1] - d[i][1];
}
}
}
void return_answer(int n) {for (int i = 1; i <= n; ++i) answer(i, a[i]);}
void solve(int n) {
for (int i = 3; i <= n; ++i) d[i][1] = query(i - 1, i), d[i][2] = query(i - 2, i);
int d12 = query(1, 2);
for (a[1] = 1; a[1] <= n; ++a[1]) {
a[2] = a[1] + d12; deduce(n);
if (check(n)) {return_answer(n); return;}
a[2] = a[1] - d12; deduce(n);
if (check(n)) {return_answer(n); return;}
}
}
