#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> construct_permutation(long long k) {
--k;
vector<int> groups;
int sum = 0;
vector<int> ans;
long long po[61];
po[0] = 1LL;
for (int i=1; i <= 59; ++i) po[i] = po[i-1]*2LL;
int cc;
for (int i=59; i >= 1; --i) {
cc = 0;
while (k >= po[i]) {
k -= po[i];
++cc;
++k;
}
if (cc == 1) {
groups.push_back(i);
sum += i;
}
else if (cc == 2) {
groups.push_back(i+1);
sum += i+1;
}
}
while (k > 0LL) {
groups.push_back(1);
--k;
++sum;
}
--sum;
int n = (int)groups.size();
for (int i=0; i < n; ++i) {
int from = sum-groups[i]+1;
for (int j=from; j <= sum; ++j) ans.push_back(j);
sum = from-1;
}
return ans;
}
