#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 best = -1;
long long bestm = (long long)4e18;
for (long long ans = 0; ans <= 400; ans++) {
if ((k + ans) % 2 == 0) continue;
long long temp = (k + ans - 1) / 2;
if (count(temp) > ans) continue;
long long cnt = 1;
long long cur = temp;
multiset<long long> bad;
while (cur > 0) {
if (cur % 2 == 1) bad.insert(cnt);
cur = cur / 2;
cnt = cnt * 2;
}
while ((long long)bad.size() < ans) {
auto dad = *bad.rbegin();
bad.erase(bad.find(dad));
bad.insert(dad / 2);
bad.insert(dad / 2);
}
long long m = 0;
for (auto u : bad) {
m += (f[u] + 1);
}
if (m < bestm) {
bestm = m;
best = ans;
}
}
long long temp = (k + best - 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() < best) {
auto dad = *bad.rbegin();
bad.erase(bad.find(dad));
bad.insert(dad / 2);
bad.insert(dad / 2);
}
long long m = 0;
for (auto u : bad) {
m += (f[u] + 1);
}
vector<int> ans;
for (auto u : bad) {
for (i = 1; i <= f[u] + 1; i++) {
ans.push_back(m - f[u] - 1 + i - 1);
}
m -= (f[u] + 1);
}
return ans;
}
