#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; 

	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 - 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;
}