#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];
unordered_map<int, bool> used;
int q( int l, int r ) {
if ( ans[l][r] == -1 )
ans[l][r] = query( l, r );
return ans[l][r];
}
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;
}
v[p1] = 1;
used[1] = true;
v[p1 + 1] = 1 + q( p1, p1 + 1 );
used[v[p1 + 1]] = true;
if ( p1 > 1 )
v[p1 - 1] = 1 + q( p1 - 1, p1 );
used[v[p1 - 1]] = true;
for ( int i = p1 + 2; i <= n; i++ ) {
int x = q( i - 1, i );
if ( v[i - 1] - x < 1 || used[v[i - 1] - x] ) {
v[i] = v[i - 1] + x;
continue;
}
if ( v[i - 1] + x > n || used[v[i - 1] + x] ) {
v[i] = v[i - 1] - x;
continue;
}
if ( v[i - 2] < v[i - 1] ) {
if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
v[i] = v[i - 1] - q( i - 1, i );
else if ( q( i - 2, i ) == q( i - 1, i ) )
v[i] = v[i - 1] - q( i - 1, i );
else
v[i] = v[i - 1] + q( i - 1, i );
} else {
if ( q( i - 2, i ) == q( i - 2, i - 1 ) )
v[i] = v[i - 1] + q( i - 1, i );
else if ( q( i - 2, i ) == q( i - 1, i ) )
v[i] = v[i - 1] + q( i - 1, i );
else
v[i] = v[i - 1] - q( i - 1, i );
}
used[v[i]] = true;
}
for ( int i = p1 - 2; i >= 1; i-- ) {
int x = q( i, i + 1 );
if ( v[i + 1] - x < 1 || used[v[i + 1] - x] ) {
v[i] = v[i + 1] + x;
continue;
}
if ( v[i + 1] + x > n || used[v[i + 1] + x] ) {
v[i] = v[i + 1] - x;
continue;
}
if ( v[i + 2] < v[i + 1] ) {
if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
v[i] = v[i + 1] - q( i, i + 1);
else if ( q( i, i + 2 ) == q( i, i + 1 ) )
v[i] = v[i + 1] - q( i, i + 1 );
else
v[i] = v[i + 1] + q( i, i + 1 );
} else {
if ( q( i, i + 2 ) == q( i + 1, i + 2 ) )
v[i] = v[i + 1] + q( i, i + 1 );
else if ( q( i, i + 2 ) == q( i, i + 1 ) )
v[i] = v[i + 1] + q( i, i + 1 );
else
v[i] = v[i + 1] - q( i, i + 1 );
}
used[v[i]] = true;
}
for ( int i = 1; i <= n; i++ )
answer( i, v[i] );
}
