#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MX = 1e15;
vector<int> construct_permutation(ll k) {
assert(k <= MX);
k--;
vector<int> perm;
vector<int> bits;
ll curr = 0;
for (int i = 0; i < 60; i++) {
curr |= (1LL << i);
if (k >= curr) {
bits.push_back(i);
}
else break;
}
curr /= 2;
k -= curr;
vector<int> after;
for (int i = 0; i < 61; i++) {
if (!((k >> i) & 1)) continue;
after.push_back(i);
for (int j = 0; j < (int)bits.size(); j++) {
if (bits[j] >= i) bits[j]++;
}
}
reverse(after.begin(), after.end());
for (auto x: bits) perm.push_back(x);
for (auto x: after) perm.push_back(x);
return perm;
}
