#include <bits/stdc++.h>

#include "perm.h"

using namespace std;

std::vector<int> construct_permutation(long long k) {
    vector<long long> bt;
    int cnt = 0;
    for (int i = 0; i <= 60; i++) {
        if (((k >> i) & 1) == 1) {
            cnt++;
            bt.emplace_back(i);
        }
    }
    if (cnt == 1) {
        vector<int> ans;
        for (int i = 0; i < bt[0]; i++) ans.emplace_back(i);
        return ans;
    }
    cnt--;
    deque<int> res;
    int cur = 0;
    sort(bt.rbegin(), bt.rend());
    for (int i = 0; i < bt[0]; i++) res.emplace_back(i);
    cur = bt[0];
    for (int i = 1; i < (int) bt.size(); i++) {
        deque<int> new_res;
        for (int j = 0; j < bt[i]; j++) new_res.emplace_back(res[j]);
        new_res.emplace_back(cur);
        for (int j = bt[i]; j < (int) res.size(); j++) new_res.emplace_back(res[j]);
        cur++;
        res = new_res;
    }
//    for (int jj = cur; jj <= cur + cnt - 1; jj++)
//        res.push_front(jj);
    vector<int> ans;
    for (int i: res) ans.emplace_back(i);
    return ans;
}