#include "xylophone.h"
#include "bits/stdc++.h"
using namespace std;
static int A[5000];
void solve(int n) {
int dis[n][n];
for (int i = 0; i < n - 1; i++) dis[i][i + 1] = query(i + 1, i + 2);
for (int i = 0; i < n - 2; i++)
{
dis[i][i + 2] = query(i + 1, i + 3);
if (dis[i][i + 2] == dis[i][i + 1]) dis[i][i + 2] = dis[i][i + 1] - dis[i + 1][i + 2];
else if (dis[i][i + 2] == dis[i + 1][i + 2]) dis[i][i + 2] = dis[i + 1][i + 2] - dis[i][i + 1];
}
for (int i = 3; i < n; i++)
{
for (int l = 0; l < n - i; l++)
{
int r = l + i;
if (dis[l][l + 1] + dis[l][l + 2] == dis[l + 1][l + 2])
{
if (dis[l + 1][r] + dis[l + 2][r] == dis[l + 1][l + 2]) dis[l][r] = abs(dis[l][l + 1] - dis[l + 1][r]);
else
{
if (dis[l + 1][r] < dis[l + 2][r]) dis[l][r] = dis[l + 1][r] + dis[l][l + 1];
else dis[l][r] = dis[l + 2][r] + dis[l][l + 2];
}
} else
{
if (dis[l + 1][r] + dis[l + 2][r] == dis[l + 1][l + 2])
{
if (dis[l][l + 1] < dis[l][l + 2]) dis[l][r] = dis[l][l + 1] + dis[l + 1][r];
else dis[l][r] = dis[l][l + 2] + dis[l + 2][r];
}
else
{
if (dis[l][l + 1] < dis[l][l + 2])
{
if (dis[l + 1][r] < dis[l + 2][r]) dis[l][r] = abs(dis[l + 1][r] - dis[l][l + 1]);
else dis[l][r] = dis[l][l + 1] + dis[l + 2][r] + dis[l + 1][l + 2];
} else
{
if (dis[l + 2][r] < dis[l + 1][r]) dis[l][r] = abs(dis[l + 2][r] - dis[l][l + 2]);
else dis[l][r] = dis[l][l + 2] + dis[l + 1][r] + dis[l + 1][l + 2];
}
}
}
}
}
int ind = -1;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (dis[i][j] == n - 1) ind = i, answer(i + 1, 1);
for (int i = 0; i < n; i++) if (i != ind) answer(i + 1, dis[min(ind, i)][max(ind, i)] + 1);
}
