#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
vector <int> construct_permutation(ll k) {
vector <int> ans;
int mx_num = 0;
vector <int> path;
while (k > 1) {
if (k % 2 == 1) path.push_back(1), k--;
else path.push_back(2), k /= 2;
}
reverse(path.begin(), path.end());
for (auto it : path) {
if (it == 1) ans.insert(ans.begin(), mx_num++);
else ans.push_back(mx_num++);
}
return ans;
}
