#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) {
long long mx = 0;
int x = -1, y = -1;
for(int i = 1; i <= 60; ++i) {
long long cur = (1ll<<i)-1;
if(cur <= k) {
if(cur>mx) {
mx = cur;
x = i;
y = -1;
}
}
for(int j = 1; j <= 60; ++j) {
long long ruc = cur+(1ll<<j)-1;
if(ruc<=k) {
if(ruc>mx) {
mx = ruc;
x = i;
y = j;
}
}
}
}
if(y == -1) {
long long cur = (1ll<<x)-1;
k -= cur;
n += x;
v.push_back({n-x, n-1});
continue;
}
long long c1 = (1ll<<x)-1;
long long c2 = (1ll<<y)-1;
k -= c1;
k -= c2;
n += x;
v.push_back({n-x, n-1});
n += y;
v.push_back({n-y, n-1});
}
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;
}
