#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
#define endl '\n'
static int A[5001];
void solve(int N) {
for (int i = 1; i <= N; i++)
A[i] = -1;
int lo = 1;
int hi = N;
int idx = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (query(mid, N) == N - 1) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
A[idx] = 1;
int done = 1;
if (idx > 1){
++done;
A[idx - 1] = query(idx - 1, idx) + 1;
}
if (idx < N){
++done;
A[idx + 1] = query(idx, idx + 1) + 1;
}
for (int j = idx - 2; j >= 1; j--) {
if (N - done <= 0) break;
int q1 = query(j, j + 2);
int q2 = query(j, j + 1);
int diff = abs(A[j + 1] - A[j + 2]);
if (diff == q1) {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] - q2;
else
A[j] = A[j + 1] + q2;
} else if (q2 == q1) {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] - q2;
else
A[j] = A[j + 1] + q2;
} else {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] + q2;
else
A[j] = A[j + 1] - q2;
}
++done;
}
for (int j = idx + 2; j <= N; j++) {
if (N - done <= 0) break;
int q1 = query(j - 2, j);
int q2 = query(j - 1, j);
int diff = abs(A[j - 1] - A[j - 2]);
if (diff == q1) {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] - q2;
else
A[j] = A[j - 1] + q2;
} else if (q2 == q1) {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] - q2;
else
A[j] = A[j - 1] + q2;
} else {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] + q2;
else
A[j] = A[j - 1] - q2;
}
++done;
}
for (int i = 1; i <= N; i++)
answer(i, A[i]);
}
