#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);
S.push_back(~0);
for (uint x = 3; x < 65; 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;
uint S63 = S[63], in = 1;
for (uint j: R[63]) {
// printf("- [%llu] - %llu\n", S63, j);
if (S63 <= (k - SM) && in <= 63) {
GN.push_back({63 - in, in});
SZ += 63;
SM += S63;
break;
}
S63 -= j, in++;
}
// GN.push_back({63, 0});
// SM += S63;
// SZ += 63;
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);
// printf("(%llu, %llu)\n", GN[x].first, GN[x].second);
assert(lsz >= GN[x].second);
if (GN[x].second)
reverse(O.begin() + offset + (lsz - GN[x].second), O.begin() + offset + lsz);
offset += lsz;
}
return O;
}
