#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(NULL));
std::vector<int> construct_permutation(long long k)
{
vector<int> ans;
k--;
int n = 0;
vector<pair<int, int> > v;
while(k>0) {
int j = -1;
int mx = 0;
for(int i = 60; i >= 1; --i) {
long long cur = (1ll<<i)-1;
if(cur <= k) {
if(cur == k) {
j = i;
break;
}
int cnt = __builtin_popcountll(k-cur);
if(cnt>mx) {
mx = cnt;
j = i;
}
}
}
int i = j;
n += i;
v.push_back({n-i, n-1});
long long cur = (1ll<<i)-1;
k -= cur;
}
reverse(v.begin(), v.end());
for(auto e : v) {
int l = e.first;
int r = e.second;
for(int i = l; i <= r; ++i) {
ans.push_back(i);
}
}
return ans;
}
