#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> construct_permutation(ll k){
vector<int> t;
ll c = 1;
int cc = 0;
while(c * 2 <= k){
t.push_back(cc++);
c *= 2;
}
k -= c;
int tmp = cc;
vector<int> ans = t;
for(ll b = 60;b>=0;b--){
if(cc >= 90) continue;
if(k & (1LL << b)){
t.push_back(t[b]);
ans.push_back(t[b]);
for(int i = b;i<cc;i++) t[i]++, ans[i]++;
++cc;
k -= (1LL << b);
}
}
vector<int> d;
for(int i = tmp;i<cc;i++) d.push_back(t[i]);
sort(d.begin(), d.end());
int ptr = 0;
vector<int> vv(d.size());
for(ll b = 0;b<(ll)d.size();b++){
if(!(k & (1LL << b))){
vv[b] = d[ptr++];
}
}
for(ll b = (ll)(d.size() - 1);b>=0;b--){
if(k & (1LL << b)){
vv[b] = d[ptr++];
}
}
for(int i = 0;i<d.size();i++) ans.pop_back();
for(int i = (int)vv.size() - 1;i>=0;i--) ans.push_back(vv[i]);
return ans;
}
