#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);
        }
    }
    bt.emplace_back(cnt);
    if (cnt == 1) {
        vector<int> ans;
        for (int i = 0; i < bt[0]; i++) ans.emplace_back(i);
        return ans;
    }
    bt.back()--;
    deque<int> res;
    int cur = 0;
    for (int j = 0; j < (int) bt.size() - 1; j++) {
        int i = bt[j];
        for (int jj = cur + i - 1; jj >= cur; jj--)
            res.push_front(jj);
        cur += i;
    }
    for (int jj = cur; jj <= cur + bt.back() - 1; jj++)
        res.push_front(jj);
    vector<int> ans;
    for (int i: res) ans.emplace_back(i);
    return ans;
}