#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
const int N = 200;
int node = 0;
vector<int> g[N];
int a[N];
vector<int> b;
void dfs(int v) {
b.push_back(a[v]);
sort(g[v].begin(), g[v].end(), [](int x, int y) {
return a[x] > a[y];
});
for (int to : g[v]) {
dfs(to);
}
}
vector<int> construct_permutation(long long k) {
if (k == 1)
return {};
while (node) {
g[node].clear();
a[node] = 0;
node--;
}
b.clear();
int mx = 63 - __builtin_clzll(k);
node = 1;
while (node < mx) {
g[node].push_back(node + 1);
++node;
}
int val = 0;
for (int i = 1; i <= mx; i++) {
a[i] = val++;
if (i < mx && (k >> i & 1)) {
g[i].push_back(++node);
a[node] = val++;
}
}
dfs(1);
if (k & 1) {
b.push_back(val++);
for (int i = (int)b.size() - 2; i >= 0; i--)
swap(b[i], b[i + 1]);
}
// for (int c : b)
// cout << c << ' ';
// cout << '\n';
return b;
}
