#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5000;
int v[MAX_N + 1], ans[MAX_N + 1][MAX_N + 1];
void solve( int n ) {
int l = 1, r = n;
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( query( mid, n ) == n - 1 )
l = mid;
else
r = mid;
}
int p1 = l;
for ( int l = 1; l <= n; l++ ) {
for ( int r = l; r <= n; r++ )
ans[l][r] = -1;
}
for ( int i = 1; i <= n - 1; i++ )
ans[i][i + 1] = query( i, i + 1 );
for ( int i = 1; i <= n - 2; i++ )
ans[i][i + 2] = query( i, i + 2 );
v[p1] = 1;
v[p1 + 1] = 1 + ans[p1][p1 + 1];
if ( p1 > 1 )
v[p1 - 1] = 1 + ans[p1 - 1][p1];
for ( int i = p1 + 2; i <= n; i++ ) {
if ( v[i - 2] < v[i - 1] ) {
if ( ans[i - 2][i] == ans[i - 2][i - 1] )
v[i] = v[i - 1] - ans[i - 1][i];
else if ( ans[i - 2][i] == ans[i - 1][i] )
v[i] = v[i - 1] - ans[i - 1][i];
else
v[i] = v[i - 1] + ans[i - 1][i];
} else {
if ( ans[i - 2][i] == ans[i - 2][i - 1] )
v[i] = v[i - 1] + ans[i - 1][i];
else if ( ans[i - 2][i] == ans[i - 1][i] )
v[i] = v[i - 1] + ans[i - 1][i];
else
v[i] = v[i - 1] - ans[i - 1][i];
}
}
for ( int i = p1 - 2; i >= 1; i-- ) {
if ( v[i + 2] < v[i + 1] ) {
if ( ans[i][i + 2] == ans[i + 1][i + 2] )
v[i] = v[i + 1] - ans[i][i + 1];
else if ( ans[i][i + 2] == ans[i][i + 1] )
v[i] = v[i + 1] - ans[i][i + 1];
else
v[i] = v[i + 1] + ans[i][i + 1];
} else {
if ( ans[i][i + 2] == ans[i + 1][i + 2] )
v[i] = v[i + 1] + ans[i][i + 1];
else if ( ans[i][i + 2] == ans[i][i + 1] )
v[i] = v[i + 1] + ans[i][i + 1];
else
v[i] = v[i + 1] - ans[i][i + 1];
}
}
for ( int i = 1; i <= n; i++ )
answer( i, v[i] );
}
