#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;
}
deque<pair<ll,ll>> arr;
ll n=0;
while(k > 0){
ll length = upper_bound(powers.begin(),powers.end(),k) - powers.begin();
if(length != 0){
length --;
}
arr.push_front({n,n+length});
// cout << k << " " << n << " to " << n + length << " " << (ll)powl(2,length)-1 <<endl;
n += length;
k -= (ll)powl(2,length)-1;
}
vector<int> ans;
for(ll i=0;i<arr.size();i++){
for(ll j=arr[i].first;j<arr[i].second;j++){
ans.pb(j);
// cout << j << " ";
}
}
// cout << endl;
return ans;
}
