#include "perm.h"
#include <cmath>
#include <deque>
#include <iostream>
#include <algorithm>
#define ll unsigned long long
#define pb push_back
using namespace std;
std::vector<int> construct_permutation(long long k)
{
if(k == 0){
return vector<int>(0);
}k--;
vector<ll> powers;
for(ll i=0;i<64;i++){
// for(int i=0;i<10;i++){
powers.pb(pow(2,i)-1);
// cout << i << " " << powers[i] << endl;
}
vector<int> ans;
ll n=0;
while(k > 0){
ll length = upper_bound(powers.begin(),powers.end(),k) - powers.begin();
if(length != 0){
length --;
}
// cout << "k-" << k << " n-" << n << " lenght-" << length << " minus-" << (ll)powl(2,length)-1 <<endl;
if(n == 0){
for(ll j=0;j<length;j++){
ans.pb(j);
}
n += length;
// cout << " ans - > ";
// for(ll j=0;j<ans.size();j++){
// cout << ans[j] << " ";
// }cout << endl;
}else{
ans.insert(ans.begin()+length-1,n);
n++;
// cout << " ans - > ";
// for(ll j=0;j<ans.size();j++){
// cout << ans[j] << " ";
// }cout << endl;
k+=length-1;
}
// cout << k << " " << n << " to " << n + length << " " << (ll)powl(2,length)-1 <<endl;
k -= (ll)powl(2,length)-1;
}
return ans;
}
