#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
deque <int> solve (int f, long long k) {
if (k == 0) return {};
deque <int> cur;
int len = 0;
for (long long i = 0; i <= 61; ++i) {
if ((1ll << i) - 1 <= k) {
len = i;
}
}
for (int j = f; j < f + len; ++j) cur.push_back(j);
deque <int> rec = solve(f + len, k - (1ll << len) + 1);
for (int i = (int) rec.size() - 1; i >= 0; --i) {
cur.push_front(rec[i]);
}
return cur;
}
vector<int> construct_permutation(long long k) {
deque<int> d = solve(0, k - 1);
vector<int> ans(d.begin(), d.end());
return ans;
}
