#include <cstdio>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
mt19937 rng(time(0));
vector<deque<int>> v;
vector<vector<int>> edg;
vector<int> res;
int last = 1;
int N;
void connect(int x, int y) {
edg[x].push_back(y);
edg[y].push_back(x);
}
void psh(int r, int x) {
vector<int> ask(N, 0);
if (v[r].size() == 1) {
connect(v[r].back(), x);
v[r].push_back(x);
} else {
fill(ask.begin(), ask.end(), 0);
ask[v[r].back() - 1] = 1;
ask[x - 1] = 1;
if (Query(ask) == 1) {
connect(v[r].back(), x);
v[r].push_back(x);
} else {
connect(v[r].front(), x);
v[r].push_front(x);
}
}
}
void uebok() {
cout << "uebki:\n";
for (auto i : v) {
for (auto j : i) {
cout << j << " ";
}
cout << "\n";
}
cout << "\n";
}
void add(int x) {
vector<int> ask(N);
for (auto i : v) {
for (auto j : i) {
ask[j - 1] = 1;
}
}
ask[x - 1] = 1;
int g = Query(ask);
if (g == last + 1) {
v.push_back({x});
} else if (g == last) {
int l = -1, r = v.size() - 1;
while (r - l - 1 > 0) {
int mid = (l + r) / 2;
fill(ask.begin(), ask.end(), 0);
for (int i = 0; i <= mid; i++) {
for (int j : v[i]) {
ask[j - 1] = 1;
}
}
ask[x - 1] = 1;
int exp = mid + 1;
// cout << exp << " " << Query(ask) << " " << mid << "\n";
if (Query(ask) == exp)
r = mid;
else
l = mid;
}
psh(r, x);
} else {
int l = -1, r = v.size() - 1;
while (r - l - 1 > 0) {
int mid = (l + r) / 2;
fill(ask.begin(), ask.end(), 0);
for (int i = 0; i <= mid; i++) {
for (int j : v[i]) {
ask[j - 1] = 1;
}
}
ask[x - 1] = 1;
int exp = mid;
if (Query(ask) == exp)
r = mid;
else
l = mid;
}
int fi = r;
r--;
l = -1;
while (r - l - 1 > 0) {
int mid = (l + r) / 2;
fill(ask.begin(), ask.end(), 0);
for (int i = 0; i <= mid; i++) {
for (int j : v[i]) {
ask[j - 1] = 1;
}
}
ask[x - 1] = 1;
int exp = mid + 1;
if (Query(ask) == exp)
r = mid;
else
l = mid;
}
// cout << fi << " " << r << "\n";
psh(r, x);
int le = v[fi].back(), ri = v[r].front();
fill(ask.begin(), ask.end(), 0);
ask[v[fi].back() - 1] = 1;
ask[x - 1] = 1;
if (Query(ask) == 1) {
connect(v[fi].back(), x);
} else {
connect(v[fi].front(), x);
}
v.erase(v.begin() + fi);
deque<int> nw;
nw.push_back(x);
int last = x, go = edg[x][0];
while (true) {
nw.push_back(go);
for (auto to : edg[go]) {
if (to == last) {
continue;
}
last = go;
go = to;
break;
}
if (go == nw.back()) {
break;
}
}
// cout << last << " " << go << "\n";
// return;
last = x;
go = edg[x][1];
while (true) {
nw.push_front(go);
for (auto to : edg[go]) {
if (to == last) {
continue;
}
last = go;
go = to;
break;
}
if (go == nw.front()) {
break;
}
}
v[r] = nw;
}
// uebok();
last = g;
}
void Solve(int N) {
vector<int> order;
edg.resize(N + 1);
::N = N;
for (int i = 2; i <= N; i++) {
order.push_back(i);
}
shuffle(order.begin(), order.end(), rng);
v.push_back({1});
for (auto i : order) {
add(i);
}
for (auto i : v[0]) {
res.push_back(i);
}
Answer(res);
}
