#include "perm.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
vector<int> construct_permutation(long long k){
vector<int> v;
ll fe = 1;
k -= 1;
int cur = 0;
while (k >= fe) {
v.pb(cur);
k -= fe;
fe *= 2LL;
cur += 1;
}
int m = ls(v);
for (int i = 60;~i;--i) {
if (k >> i & 1) {
v.pb(i);
}
}
for (int i = ls(v) - 1;i >= m;--i) {
int x = v[i];
for (int j = x;j<m;++j) {
v[j] += 1;
}
v[i] = (~(x - 1) ? v[x - 1] : -1) + 1;
}
// for (auto it:v) cout << it << ' ';
// cout << endl;
return v;
}
