#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
int A[5005];
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;
bool done[N + 5] = {};
done[1] = 1;
for (int i = idx + 1; i <= N; i ++){
int d = query(i, i + 1);
int x = A[i - 1] + d, y = A[i - 1] - d;
if (x > N or done[x]) A[i] = y;
else if (y <= 0 or done[y]) A[i] = x;
else{
d = query(i - 1, i + 1);
if (A[i - 2] < A[i - 1]){
if (d == x - A[i - 2])
A[i] = x;
else
A[i] = y;
}
else{
if (d == A[i - 2] - y)
A[i] = y;
else
A[i] = x;
}
}
done[A[i]] = 1;
}
for (int i = 1; i <= N; i++)
answer(i, A[i]);
}
