#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;
// cerr << "L: " << L << " R: " << R << "\n";
vector<int> ans(N+1, -1);
set<int> avail; for (int i = 1; i <= N; i++) avail.insert(i);
// avail.erase(1);
// avail.erase(N);
ans[L] = 1;
// ans[R] = N;
for (int i = L+1; i <= N; i++) {
if (i == L+1) {
ans[i] = 1 + query(L, i);
// cerr << "Options for " << i << " are " << ans[i] << "\n";
} else {
int dx = query(i-1, i);
int a = ans[i-1] + dx, b = ans[i-1] - dx;
int x = ans[i-2], y = ans[i-1];
// cerr << "Options for " << i << " are " << a << " and " << b << "\n";
// cerr << "i: " << i << " dx: " << dx << " dy: " << dy << " a: " << a << " b: " << b << " x: " << x << " y: " << y << "\n";
// y < a < x, y < x < a, x < y < a
// x < b < y, b < y < x, b < x < y
if (!avail.count(a)) ans[i] = b;
else if (!avail.count(b)) ans[i] = a;
else {
int dy = query(i-2, i);
if (y < a && a < x && dy == x-y) ans[i] = a;
else if (y < x && x < a && dy == a-y) ans[i] = a;
else if (x < y && y < a && dy == a-x) ans[i] = a;
else if (x < b && b < y && dy == y-x) ans[i] = b;
else if (b < y && y < x && dy == x-b) ans[i] = b;
else if (b < x && x < y && dy == y-b) ans[i] = b;
}
}
// avail.erase(ans[i]);
}
for (int i = L-1; i >= 1; i--) {
if (i == L-1) {
ans[i] = 1 + query(i, L);
} else {
int dx = query(i, i+1);
int a = ans[i+1] + dx, b = ans[i+1] - dx;
int x = ans[i+2], y = ans[i+1];
// y < a < x, y < x < a, x < y < a
// x < b < y, b < y < x, b < x < y
if (!avail.count(a)) ans[i] = b;
else if (!avail.count(b)) ans[i] = a;
else {
int dy = query(i, i+2);
if (y < a && a < x && dy == x-y) ans[i] = a;
else if (y < x && x < a && dy == a-y) ans[i] = a;
else if (x < y && y < a && dy == a-x) ans[i] = a;
else if (x < b && b < y && dy == y-x) ans[i] = b;
else if (b < y && y < x && dy == x-b) ans[i] = b;
else if (b < x && x < y && dy == y-b) ans[i] = b;
}
}
// avail.erase(ans[i]);
}
// 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);
// int a = ans[i-1] + dx, b = ans[i-1] - dx;
// int x = ans[i-2], y = ans[i-1];
// // y < a < x, y < x < a, x < y < a
// // x < b < y, b < y < x, b < x < y
// if (!avail.count(a)) ans[i] = b;
// else if (!avail.count(b)) ans[i] = a;
// else {
// int dy = query(i-2, i);
// if (y < a && a < x && dy == x-y) ans[i] = a;
// else if (y < x && x < a && dy == a-y) ans[i] = a;
// else if (x < y && y < a && dy == a-x) ans[i] = a;
// else if (x < b && b < y && dy == y-x) ans[i] = b;
// else if (b < y && y < x && dy == x-b) ans[i] = b;
// else if (b < x && x < y && dy == y-b) ans[i] = b;
// }
// }
// avail.erase(ans[i]);
// }
// for (int i = 1; i <= N; i++) cerr << ans[i] << " ";
// cerr << "\n";
for(int i = 1; i <= N; i++) {
answer(i, ans[i]);
}
}
