#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
void solve(int N) {
int value = query(1, N);
int L = 1, R = N;
int lo = 1, hi = N;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (query(1, mid) == value) {
hi = mid;
} else {
lo = mid + 1;
}
}
R = lo;
lo = 1, hi = N;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (query(mid, N) == value) {
lo = mid;
} else {
hi = mid - 1;
}
}
L = lo;
vector<int> ans(N+1, -1);
ans[L] = 1; ans[R] = N;
for (int i = L+1; i < R; i++) {
if (i == L+1) {
ans[i] = 1 + query(L, i);
} else {
int dx = query(i-1, i), dy = query(i-2, i);
int a = ans[i-1] + dx, b = ans[i-1] - dx;
int x = ans[i-2], y = ans[i-1];
if (x < y && dy == a-x) ans[i] = a;
else if (x > y && dy == x-y) ans[i] = a;
else if (x < y && dy == y-x) ans[i] = b;
else if (x > y && dy == x-b) ans[i] = b;
}
}
for (int i = L-1; i >= 1; i--) {
if (i == L-1) {
ans[i] = 1 + query(i, L);
} else {
int dx = query(i+1, i), dy = query(i+2, i);
int a = ans[i+1] + dx, b = ans[i+1] - dx;
int x = ans[i+2], y = ans[i+1];
if (x < y && dy == a-x) ans[i] = a;
else if (x > y && dy == x-y) ans[i] = a;
else if (x < y && dy == y-x) ans[i] = b;
else if (x > y && dy == x-b) ans[i] = b;
}
}
for (int i = R+1; i <= N; i++) {
if (i == R+1) {
ans[i] = N - query(R, i);
} else {
int dx = query(i-1, i), dy = query(i-2, i);
int a = ans[i-1] + dx, b = ans[i-1] - dx;
int x = ans[i-2], y = ans[i-1];
if (x < y && dy == a-x) ans[i] = a;
else if (x > y && dy == x-y) ans[i] = a;
else if (x < y && dy == y-x) ans[i] = b;
else if (x > y && dy == x-b) ans[i] = b;
}
}
// for (int i = 1; i <= N; i++) cerr << ans[i] << " ";
// cerr << "\n";
for(int i = 1; i <= N; i++) {
answer(i, ans[i]);
}
}
