/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <int> construct_permutation (ll k) {
int bits = 63 - __builtin_clzll(k);
int len = bits + __builtin_popcountll(k) - 1;
if (len <= 90) {
vector <int> p;
int l = 1, r = len;
for (int e = 0; e < bits; e++) {
if ((k >> e) & 1) {
p.push_back(r--);
}
p.push_back(l++);
}
return p;
} else {
vector <int> p = construct_permutation(k / 3);
int len = (int) p.size();
vector <int> q;
for (int i = 1; i <= k % 3; i++) {
q.push_back(i);
}
for (int x : p) {
q.push_back(x);
}
q.push_back(len + 2);
q.push_back(len + 1);
return q;
}
}
