#include "perm.h"
//OP
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
using namespace std;
vector<int> construct_permutation(long long k)
{
vector<int> ans;
int mx_num = 0;
vector<int> path;
while (k > 1) {
if (k & 1) path.pb(1), k--;
else path.pb(0), k /= 2;
}
reverse(all(path));
for (auto it : path) {
if (it) ans.insert(ans.begin(), mx_num++);
else ans.pb(mx_num++);
}
return ans;
}
//ED
