#include "xylophone.h"
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
/**
* JOI Open 2018 - Xylophone
* Vaqt murakkabligi: O(N)
* So'rovlar soni: ~2N
*/
void solve(int N) {
vector<int> A(N + 1);
vector<int> diff1(N + 1); // query(i, i+1)
vector<int> diff2(N + 1); // query(i, i+2)
vector<bool> used(N + 1, false);
// 1. Eng past tovush (1) indeksini topamiz
int low = 1, high = N, first_pos = 1;
while (low <= high) {
int mid = (low + high) / 2;
if (query(mid, N) == N - 1) {
first_pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
A[first_pos] = 1;
used[1] = true;
// 2. O'ng tomonga qarab aniqlash
if (first_pos < N) {
A[first_pos + 1] = 1 + query(first_pos, first_pos + 1);
used[A[first_pos + 1]] = true;
for (int i = first_pos + 2; i <= N; i++) {
int d1 = query(i - 1, i);
int d2 = query(i - 2, i);
// Ikki xil ehtimol bor: A[i-1] + d1 yoki A[i-1] - d1
int opt1 = A[i - 1] + d1;
int opt2 = A[i - 1] - d1;
if (opt1 > N || used[opt1]) A[i] = opt2;
else if (opt2 < 1 || used[opt2]) A[i] = opt1;
else {
// Yo'nalishni query(i-2, i) orqali aniqlaymiz
int real_max = max({A[i - 2], A[i - 1], opt1});
int real_min = min({A[i - 2], A[i - 1], opt1});
if (real_max - real_min == d2) A[i] = opt1;
else A[i] = opt2;
}
used[A[i]] = true;
}
}
// 3. Chap tomonga qarab aniqlash (agar bo'lsa)
for (int i = first_pos - 1; i >= 1; i--) {
int d1 = query(i, i + 1);
int opt1 = A[i + 1] + d1;
int opt2 = A[i + 1] - d1;
if (opt1 > N || used[opt1]) A[i] = opt2;
else if (opt2 < 1 || used[opt2]) A[i] = opt1;
else {
int d2 = query(i, i + 2);
int real_max = max({opt1, A[i + 1], A[i + 2]});
int real_min = min({opt1, A[i + 1], A[i + 2]});
if (real_max - real_min == d2) A[i] = opt1;
else A[i] = opt2;
}
used[A[i]] = true;
}
for (int i = 1; i <= N; i++) answer(i, A[i]);
}
