#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
long long count(long long x) {
long long bit = 0;
while (x > 0) {
bit += x % 2;
x = x / 2;
}
return bit;
}
vector<int> construct_permutation(long long k) {
map<long long, long long> f;
long long d = 1, i;
f[1] = 0;
for (i = 1; i <= 60; i++) {
d = d * 2;
f[d] = i;
}
long long ans = -1;
for (long long i = 0; i <= 400; i++) {
if ((k + i) % 2 == 1) {
long long sad = (k + i - 1) / 2;
if (count(sad) <= i) {
ans = i;
break;
}
}
}
long long temp = (k + ans - 1) / 2;
long long cnt = 1;
multiset<long long> bad;
while (temp > 0) {
if (temp % 2 == 1) bad.insert(cnt);
temp = temp / 2;
cnt = cnt * 2;
}
while ((long long)bad.size() < ans) {
auto it = bad.lower_bound(2); // smallest x >= 2
long long dad = *it;
bad.erase(it);
bad.insert(dad / 2);
bad.insert(dad / 2);
}
long long m = 0;
for (auto u : bad) {
m += (f[u] + 1);
}
vector<int> res;
for (auto u : bad) {
for (i = 1; i <= f[u] + 1; i++) {
res.push_back(m - f[u] - 1 + i - 1);
}
m -= (f[u] + 1);
}
return res;
}
