#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
#include "perm.h"
vector<int> construct_permutation(long long k)
{
long long xd = __builtin_popcountll(k);
long long n = __lg(k) + xd - 1;
vector<int> ans(n,0);
long long p1 = __lg(k) - 1;
long long p2 = __lg(k);
long long val = n - 1;
vector<int> bits;
for(int i=__lg(k)-1;i>=0;i--){
if(k>>i&1) bits.push_back(i);
}
ans[p1--]=val--;
for(int x:bits){
while(p1+1>x) ans[p1--]=val--;
ans[p2++]=val--;
}
while(val>=0) ans[p1--]=val--;
return ans;
}
/*void _(){
int k;
cin >> k;
int xd = __builtin_popcountll(k);
int n = __lg(k) + xd - 1;
vector<int> ans(n,0);
int p1 = __lg(k) - 1;
int p2 = __lg(k);
int val = n - 1;
vector<int> bits;
for(int i=__lg(k)-1;i>=0;i--){
if(k>>i&1) bits.push_back(i);
}
ans[p1--]=val--;
for(int x:bits){
while(p1+1>x) ans[p1--]=val--;
ans[p2++]=val--;
}
while(val>=0) ans[p1--]=val--;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
