#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;
for(int i = 60; i >= 0; --i) {
long long cur = (1ll<<i)-1;
if(cur <= k) {
j = i;
break;
}
}
int x = rng()%3;
int i = max(0, j-x);
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;
}
