#include "perm.h"
#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int INF = 1e9; 

vector<int> construct_permutation(i64 k) {
    int len = 0; 
    // 1 2 4 8 16 32 64 128 256 512 

    while (k >= (1ll << len)) ++len; 
    
    --len; 

    k -= 1 << len; 
    vector<int> a(len + 5, -1), ans, b;
    int mn = -1, se = -1;
    for (int i = len - 1; i >= 0; --i)
        if (k >> i & 1) {
            if (i && (k >> i - 1 & 1) && mn != -1 && se != -1) {
                --a[mn]; 
                a[i - 1] = a[se]; 
                --a[se]; 
                --i; 
            } else if (mn != -1) a[i] = a[mn] - 1, se = mn, mn = i; 
            else a[i] = INF - 1, mn = i; 
        }
    for (int i = 0; i < len; ++i) {
        if (a[i] != -1) ans.push_back(a[i]); 
        ans.push_back(INF * 2 - i); 
    }
    reverse(ans.begin(), ans.end()); b = ans; sort(b.begin(), b.end()); 
    for (int &i : ans) 
        i = lower_bound(b.begin(), b.end(), i) - b.begin(); 
    return ans;
}