#include "perm.h"
// author: yanybayev
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
vector<int> construct_permutation(long long k){
vector<int> v;
ll fe = 1, p = 0, cur = 0, ok = 0;
while (fe * 2 <= k) {
fe *= 2;
p += 1;
}
for (int i = p - 1;~i;--i) {
v.pb(cur ++);
if (k >> i & 1) {
if (i and (k >> (i - 1) & 1) and ok) v.pb(cur ++), v.insert(begin(v) + 2, cur ++), i--;
else v.insert(begin(v), cur ++), ok += 1;
}
}
return v;
}
