#include <bits/stdc++.h>
#include "xylophone.h"
#define pb push_back
using namespace std;
bool f[5005];
int n, a[5005];
void slv(int x) {
if (x == 1) return ;
a[x - 1] = 1 + query(x - 1, x);
for (int i = x - 2; i >= 1; --i) {
int v2 = query(i, i + 1);
int ps1 = a[i + 1] + v2;
int ps2 = a[i + 1] - v2;
int mx = max(a[i + 1], a[i + 2]);
int mn = min(a[i + 1], a[i + 2]);
if (ps1 > n || f[ps1]) a[i] = ps2, f[ps2] = true;
else
if (ps2 < 1 || f[ps2]) a[i] = ps1, f[ps1] = true;
else {
int v3 = query(i, i + 2);
if (max(mx, ps1) - min(mn, ps1) == v3) a[i] = ps1;
else
if (max(mx, ps2) - min(mn, ps2) == v3) a[i] = ps2;
}
}
}
void srv(int x) {
a[x + 1] = 1 + query(x, x + 1);
for (int i = x + 2; i <= n; ++i) {
int v2 = query(i - 1, i);
int ps1 = a[i - 1] + v2;
int ps2 = a[i - 1] - v2;
int mx = max(a[i - 1], a[i - 2]);
int mn = min(a[i - 1], a[i - 2]);
if (ps1 > n || f[ps1]) a[i] = ps2, f[ps2] = true;
else
if (ps2 < 1 || f[ps2]) a[i] = ps1, f[ps1] = true;
else {
int v3 = query(i - 2, i);
if (max(mx, ps1) - min(mn, ps1) == v3) a[i] = ps1;
else
if (max(mx, ps2) - min(mn, ps2) == v3) a[i] = ps2;
}
}
}
void solve(int N) {
n = N;
int l = 1, r = n - 1, mid, res = -1;
while (l <= r) {
int mid = ((l + r) >> 1);
if (query(mid, n) == n - 1) {
l = mid + 1, res = mid;
}
else {
r = mid - 1;
}
}
f[1] = a[res] = 1, slv(res), srv(res);
for(int i = 1; i <= n; i++) {
answer(i, a[i]);
}
}
