#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> construct_permutation(long long k){
k--;
vector< int > ret;
int mx = 0;
while((1LL << (mx + 1)) <= k)
mx++;
int a = 0;
for(int i = 0 ;i <= mx;i++){
if(((k >> i) & 1) == 1)
a++;
}
if(a == mx + 1){
for(int i = 0 ;i <= mx;i++)
ret.push_back(i);
return ret;
}
for(int i = 0 ;i < mx;i++)
ret.push_back(i);
k -= (1LL << mx) - 1;
bool add = false;
a = 0;
mx = 0;
while((1LL << (mx + 1)) <= k)
mx++;
for(int i = 0 ;i <= mx;i++){
if(((k >> i) & 1) == 1)
a++;
}
if(a > mx + 1 - a){
k--;
add = true;
}
for(int i = 59 ;i >= 0;i--){
if(((k >> i) & 1) == 1){
ret.insert(ret.begin() + i , (int)ret.size());
}
}
if(add)
ret.insert(ret.begin(), (int)ret.size());
return ret;
}
