#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned long long
vector<int> construct_permutation(long long k) {
vector<int> O;
vector<vector<long long>> R;
R.push_back({}); // 0
R.push_back({}); // 1
R.push_back({1}); // 2
vector<uint> S;
S.push_back(1);
S.push_back(1);
for (uint x = 2; x < 64; x++)
S.push_back((S[x - 1] + 1) * 2 - 1);
for (uint x = 3; x < 64; x++) {
R.push_back({});
for (uint i: R[x - 1])
R[x].push_back(i * 2);
R[x].push_back(R[x - 1][R[x - 1].size() - 1] + 1);
}
vector<pair<uint, uint>> GN;
uint SM = 1, SZ = 0;
while (SM < k) {
for (uint i = R.size() - 1; i > 0; i--) {
if (S[i] <= (k - SM)) {
// printf("%llu: %llu\n", i, S[i]);
SM += S[i];
SZ += i;
GN.push_back({i, 0});
break;
}
}
}
for (uint x = 0; x < SZ; x++)
O.push_back(SZ - x - 1);
uint offset = 0;
for (uint x = 0; x < GN.size(); x++) {
uint lsz = GN[x].first + GN[x].second;
reverse(O.begin() + offset, O.begin() + offset + lsz);
offset += lsz;
}
return O;
}
