#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void recal(vector<int> &p){
vector<pair<int, int>> v;
for(int i = 0;i<p.size();i++) v.push_back({p[i], i});
sort(v.begin(), v.end());
for(int i = 0;i<v.size();i++) p[v[i].second] = i;
}
vector<int> construct_permutation(ll k){
vector<int> ans, b;
while(k) b.push_back(k & 3), k /= 4;
if(b.back() == 2) ans.push_back(0);
else if(b.back() == 3) ans.push_back(1), ans.push_back(0);
for(int i = (int)b.size() - 2;i>=0;i--){
if(b[i] == 0) ans.push_back(1e9), ans.push_back(2e9);
else if(b[i] == 1) ans.push_back(1e9), ans.push_back(1e9 + 1), ans.push_back(-1);
else if(b[i] == 2) ans.push_back(1e9), ans.push_back(-1), ans.push_back(2e9);
else{
int p0, p1;
for(int j = 0;j<ans.size();j++){
if(ans[j] == 0) p0 = j;
else if(ans[j] == 1) p1 = j;
}
if(p1 < p0){
for(int j = 0;j<ans.size();j++) if(ans[j] <= 1) --ans[j];
ans.push_back(1e9);
ans.push_back(2e9);
ans.push_back(1);
}else{
ans.push_back(1e9);
ans.push_back(-1);
ans.push_back(2e9);
ans.push_back(-2);
}
}
recal(ans);
}
return ans;
}
