#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
function<void(string)> add_element;
function<void()> compile_set;
function<bool(string)> check_element;
#else
#include "messy.h"
#endif
vector<int> restore_permutation(int n, int, int) {
int k = __builtin_ctz(n);
for (int i = 0; i < k; i++) {
string s(n, '0');
s[i] = '1';
add_element(s);
}
for (int i = 0; i < k - 1; i++) {
string s(n, '0');
s[i] = s[i + 1] = '1';
add_element(s);
}
vector<vector<int>> cnt(k, vector<int>(n));
for (int i = k; i < n; i++) {
for (int j = 0; j < k; j++) {
if (i & (1 << j)) {
string s(n, '0');
s[i] = s[j] = '1';
add_element(s);
}
}
int pp = 0;
for (int j = k - 1; j >= 0; j--) {
pp |= i & (1 << j);
cnt[j][pp]++;
}
}
{
string s(n, '1');
s[0] = '0';
add_element(s);
}
compile_set();
vector<int> p(n, -1);
set<int> st;
for (int i = 0; i < n; i++) {
string s(n, '0');
s[i] = '1';
if (check_element(s)) {
st.emplace(i);
}
}
vector<int> q(k);
for (int i : st) {
string s(n, '1');
s[i] = '0';
if (check_element(s)) {
q[0] = i;
st.erase(i);
break;
}
}
for (int i = 1; i < k - 1; i++) {
for (int j : st) {
string s(n, '0');
s[q[i - 1]] = s[j] = '1';
if (check_element(s)) {
q[i] = j;
st.erase(j);
break;
}
}
}
q[k - 1] = *st.begin();
for (int i = 0; i < k; i++) {
p[q[i]] = i;
}
for (int j = k - 1; j >= 0; j--) {
for (int i = 0; i < n; i++) {
if (p[i] >= 0) {
continue;
}
int pp = ~p[i];
if (cnt[j][pp] == 0) {
p[i] ^= 1 << j;
cnt[j][~p[i]]--;
continue;
}
pp ^= 1 << j;
if (cnt[j][pp] == 0) {
cnt[j][~p[i]]--;
continue;
}
string s(n, '0');
s[i] = s[q[j]] = '1';
if (check_element(s)) {
p[i] ^= 1 << j;
}
cnt[j][~p[i]]--;
}
}
for (int i = 0; i < n; i++) {
p[i] = max(p[i], ~p[i]);
}
return p;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
vector<string> t;
int cnt0 = 0;
int cnt1 = 0;
add_element = [&](string x) {
cnt0++;
t.emplace_back(x);
};
compile_set = [&]() {
for (string& x : t) {
string y = x;
for (int i = 0; i < n; i++) {
x[p[i]] = y[i];
}
}
sort(t.begin(), t.end());
};
check_element = [&](string x) {
cnt1++;
return binary_search(t.begin(), t.end(), x);
};
auto q = restore_permutation(n, 0, 0);
for (int i = 0; i < n; i++) {
assert(q[p[i]] == i);
}
debug(cnt0, cnt1);
return 0;
}
#endif
