#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
static int A[5000];
static bool mk[5000];
int get(int i) { return A[i - 1]; }
bool check(int x) { return mk[x - 1]; }
void Answer(int i, int x) {
A[i - 1] = x;
mk[x - 1] = true;
answer(i, x);
}
void solve(int N) {
int posN = -1;
{ // binsearch posN
int le = 1, ri = N;
while (le <= ri) {
int mid = (le + ri) >> 1;
if (query(1, mid) == N - 1) ri = mid - 1, posN = mid;
else le = mid + 1;
}
}
assert(posN != -1);
Answer(posN, N);
{ // posN + 1 to N;
for (int i = posN + 1; i <= N; ++i) {
int value = query(i - 1, i);
if (i == posN + 1) {
Answer(i, N - value);
continue;
}
int x = get(i - 2), y = get(i - 1);
if (y + value > N || check(y + value) ||
y - value < 1 || check(y - value)) {
if (y + value > N || check(y + value)) Answer(i, y - value);
else Answer(i, y + value);
continue;
}
int value2 = query(i - 2, i);
for (const auto& z : {y - value, y + value}) {
int max2 = max({x, y, z}), min2 = min({x, y, z});
if (max2 - min2 == value2) {
Answer(i, z);
break;
}
}
}
}
{ // posN - 1 to 1
for (int i = posN - 1; i >= 1; --i) {
int value = query(i, i + 1);
if (i == posN - 1) {
Answer(i, N - value);
continue;
}
int x = get(i + 2), y = get(i + 1);
if (y + value > N || check(y + value) ||
y - value < 1 || check(y - value)) {
if (y + value > N || check(y + value)) Answer(i, y - value);
else Answer(i, y + value);
continue;
}
int value2 = query(i, i + 2);
for (const auto& z : {y - value, y + value}) {
int max2 = max({x, y, z}), min2 = min({x, y, z});
if (max2 - min2 == value2) {
Answer(i, z);
break;
}
}
}
}
}
