#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
map<array<int, 2>, int> mp;
int ask(int l, int r) {
if(mp.count({l, r})) return mp[{l, r}];
return mp[{l, r}] = query(l + 1, r + 1);
}
int find_one(int n) {
int l = 0, r = n - 1;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(ask(mid, n - 1) == n - 1) l = mid;
else r = mid - 1;
}
return l;
}
void solve(int n) {
int i1 = find_one(n);
vector<int> a(n);
a[i1] = 1;
set<int> used;
used.emplace(1);
auto can = [&](int x) {
return x >= 1 && x <= n && !used.count(x);
};
vector<int> dif(n);
for(int i = 1; i < n; i++) {
dif[i] = ask(i - 1, i);
}
for(int i = i1 + 1; i < n; i++) {
bool bigger = false;
int x = dif[i];
if(i == i1 + 1) {
bigger = true;
} else if(!can(a[i - 1] + x)) {
// less
} else if(!can(a[i - 1] - x)) {
bigger = true;
} else {
int y = ask(i - 2, i);
if(a[i - 2] < a[i - 1]) {
if(dif[i - 1] + dif[i] == y) {
bigger = true;
} else {
// less
}
} else {
if(dif[i - 1] + dif[i] == y) {
// less
} else {
bigger = true;
}
}
}
a[i] = a[i - 1] + (bigger ? x : -x);
used.emplace(a[i]);
}
for(int i = i1 - 1; i >= 0; i--) {
bool bigger = false;
int x = dif[i + 1];
if(i == i1 - 1) {
bigger = true;
} else if(!can(a[i + 1] + x)) {
// less
} else if(!can(a[i + 1] - x)) {
bigger = true;
} else {
int y = ask(i, i + 2);
if(a[i + 2] < a[i + 1]) {
if(dif[i + 2] + dif[i + 1] == y) {
bigger = true;
} else {
// less
}
} else {
if(dif[i + 2] + dif[i + 1] == y) {
// less
} else {
bigger = true;
}
}
}
a[i] = a[i + 1] + (bigger ? x : -x);
used.emplace(a[i]);
}
// cout << "here: " << nl;
// for(int i = 0; i < n; i++) {
// cout << a[i] << ' ';
// }
// cout << nl;
for(int i = 0; i < n; i++) answer(i + 1, a[i]);
}
/**
**/
