#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int a[5001], qq[5001][5001];
int ask(int l, int r)
{
if (qq[l][r] != -1) return qq[l][r];
return qq[l][r] = query(l, r);
}
void calc(int l, int r, int f, int up)
{
if (r - l <= 1) return;
if (!f)
{
int x = ask(l + 1, r);
int lx = l + 1, rx = r - 1;
while (lx < rx)
{
int mid = (lx + rx + 1) >> 1;
int y = ask(mid, r);
if (x == y) lx = mid;
else rx = mid - 1;
}
if (up) a[lx] = a[r] + x;
else a[lx] = a[r] - x;
calc(l, lx, 0, up ^ 1), calc(lx, r, 0, up);
}
else
{
int x = ask(l, r - 1);
int lx = l + 1, rx = r - 1;
while (lx < rx)
{
int mid = (lx + rx) >> 1;
int y = ask(l, mid);
if (x == y) rx = mid;
else lx = mid + 1;
}
if (up) a[lx] = a[l] + x;
else a[lx] = a[l] - x;
calc(l, lx, 1, up), calc(lx, r, 1, up ^ 1);
}
}
void solve(int N)
{
for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) qq[i][j] = -1;
int l = 1, r = N;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (ask(mid, N) == N - 1) l = mid;
else r = mid - 1;
}
a[l] = 1;
calc(0, l, 0, 1), calc(l, N + 1, 1, 1);
for (int i = 1; i <= N; i++)
{
answer(i, a[i]);
}
}
