#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> construct_permutation(long long k) {
vector<int> op;
while (k > 1) {
if (k&1) {
op.push_back(-1);
k--;
} else {
op.push_back(1);
k/=2;
}
}
deque<int> ans;
int cur = 0;
reverse(op.begin(), op.end());
for (int &v : op) {
if (v==-1) {
ans.push_front(cur);
}
else {
for (int &x : ans) x++;
ans.push_front(0);
}
cur++;
}
vector<int> res;
for (int &v : ans) res.push_back(v);
//for (int &v : ans) cout << v << '\n';
return res;
}
