#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
std::vector<int> construct_permutation(long long k) {
vector<int> p;
vector<int> bits;
k--;
long long s = 0;
while(k > 0){
for(int i = 63 ; i >= 1; i--){
if((1ll << i) - 1 <= k){
bits.pb(i);
k -= (1ll << i) - 1;
s += i;
break;
}
}
}
// if(k == 1){
// for(int i = bits.size() - 1; i >= 0; i--){
// if(bits[i] != 1){
// int hi = bits[i];
// bits.erase(bits.begin() + i);
// bits.push_back(hi - 1);
// bits.push_back(hi - 1);
// s -= hi;
// s += 2 * hi - 2;
// break;
// }
// }
// }
s--;
for(int i : bits){
int cnt = s - i + 1;
for(int j = cnt; j <= s; j++) p.pb(j);
s -= i;
}
return p;
}
