#include <bits/stdc++.h>
#include "xylophone.h"
#define pb push_back
using namespace std;
int n, a[5005];
void slv(int x) {
if (x == 1) return ;
vector < int > v2, v3;
for (int i = x; i >= 1; --i) {
if (i - 1 >= 1) v2.pb(query(i - 1, i));
if (i - 2 >= 1) v3.pb(query(i - 2, i));
}
a[x - 1] = 1 + v2[0];
int i2 = 1, i3 = 0;
for (int i = x - 2; i >= 1; --i) {
int ps1 = a[i + 1] + v2[i2];
int ps2 = a[i + 1] - v2[i2];
int mx = max(a[i + 1], a[i + 2]);
int mn = min(a[i + 1], a[i + 2]);
if (ps1 > n) a[i] = ps2;
else
if (ps2 < 1) a[i] = ps1;
else
if (max(mx, ps1) - min(mn, ps1) == v3[i3]) a[i] = ps1;
else
if (max(mx, ps2) - min(mn, ps2) == v3[i3]) a[i] = ps2;
++i2, ++i3;
}
}
void srv(int x) {
vector < int > v2, v3;
for (int i = x; i <= n; ++i) {
if (i + 1 <= n) v2.pb(query(i, i + 1));
if (i + 2 <= n) v3.pb(query(i, i + 2));
}
a[x + 1] = 1 + v2[0];
int i2 = 1, i3 = 0;
for (int i = x + 2; i <= n; ++i) {
int ps1 = a[i - 1] + v2[i2];
int ps2 = a[i - 1] - v2[i2];
int mx = max(a[i - 1], a[i - 2]);
int mn = min(a[i - 1], a[i - 2]);
if (ps1 > n) a[i] = ps2;
else
if (ps2 < 1) a[i] = ps1;
else
if (max(mx, ps1) - min(mn, ps1) == v3[i3]) a[i] = ps1;
else
if (max(mx, ps2) - min(mn, ps2) == v3[i3]) a[i] = ps2;
++i2, ++i3;
}
}
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;
}
}
a[res] = 1, slv(res), srv(res);
for(int i = 1; i <= n; i++) {
answer(i, a[i]);
}
}
