#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(const int N) {
if (N == 1) {
answer(1, 1);
return;
}
vector<int> div1(N+1, 0);
for (int i = 1; i <= N-1; ++i) {
div1[i] = query(i, i+1);
}
vector<int> div2(N+1, 0);
for (int i = 1; i <= N-2; ++i) {
div2[i] = query(i, i+2);
}
vector<int> ss(N+1, 0);
ss[1] = +1;
for (int i = 1; i <= N-2; ++i) {
if (div2[i] == div1[i] + div1[i+1]) {
ss[i+1] = ss[i];
} else {
ss[i+1] = -ss[i];
}
}
vector<long long> val(N+1, 0);
val[1] = 0;
for (int i = 1; i <= N-1; ++i) {
val[i+1] = val[i] + 1LL * ss[i] * div1[i];
}
vector<pair<long long,int>> a;
a.reserve(N);
for (int i = 1; i <= N; ++i) {
a.push_back({val[i], i});
}
sort(a.begin(), a.end());
vector<int> rank(N+1, 0);
for (int r = 0; r < N; ++r) {
rank[a[r].second] = r + 1;
}
int pos_min = -1, pos_max = -1;
for (int i = 1; i <= N; ++i) {
if (rank[i] == 1) {
pos_min = i;
}
if (rank[i] == N) {
pos_max = i;
}
}
if (pos_min >= pos_max) {
for (int i = 1; i <= N; ++i) {
rank[i] = N - rank[i] + 1;
}
}
for (int i = 1; i <= N; ++i) {
answer(i, rank[i]);
}
}
