#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
vector<int> construct_permutation(long long x) {
vector<int> cur;
int a = 1;
cur.emplace_back(a);
while ((1LL << (a + 1)) <= x) {
a++;
cur.emplace_back(a);
}
vector<int> res;
int sz = (int) cur.size();
for (int i = 0; i < sz; i++) {
res.emplace_back(cur[i]);
if ((x >> (sz - i - 1) & 1)) {
res.emplace_back(1);
}
}
int idx = 0;
set<int> s;
for (int i = (int) res.size() - 1; i >= 0; i--) {
if (res[i] == 1) {
res[i] = idx;
s.insert(i);
idx++;
}
}
for (int i = 0; i < (int) res.size(); i++) {
if (!s.count(i)) {
res[i] = idx;
idx++;
}
}
return res;
}
