#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 cand = 0; cand <= 600; cand++) {
if ((k + cand) % 2 == 0) continue;
long long temp = (k + cand - 1) / 2;
if (count(temp) > cand) continue;
multiset<long long> bad;
long long cur = temp;
long long cnt = 1;
while (cur > 0) {
if (cur % 2 == 1) bad.insert(cnt);
cur = cur / 2;
cnt = cnt * 2;
}
bool ok = true;
while ((long long)bad.size() < cand) {
auto it = bad.lower_bound(2);
if (it == bad.end()) {
ok = false;
break;
}
long long dad = *it;
bad.erase(it);
bad.insert(dad / 2);
bad.insert(dad / 2);
}
if (!ok) continue;
long long m = 0;
for (auto u : bad) {
m += (f[u] + 1);
}
if (m < bestm) {
bestm = m;
best = cand;
}
}
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 it = bad.lower_bound(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> ans;
for (auto u : bad) {
for (i = 1; i <= f[u] + 1; i++) {
ans.push_back((int)(m - f[u] - 1 + i - 1));
}
m -= (f[u] + 1);
}
return ans;
}
