#include "perm.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
vector<int> construct_permutation(long long k)
{
vector<int> a;
while(k>0){
a.push_back(k%4);
k/=4;
}
reverse(a.begin(),a.end());
vector<int> ans;
vector<double> b,c;
if(a[0]==2){
b.pb(0);
}
else if(a[0]==3){
b.pb(1);
b.pb(0);
}
int sz=(int)a.size();
for(int i=1;i<sz;i++){
bool ok,ok1;
ok=ok1=0;
for(auto x:b){
if(x==1){
ok1=1;
}
else if(x==0 && ok1){
ok=1;
}
}
if(a[i]==0){
b.pb(1e9);
b.pb(1e9+1);
}
else if(a[i]==1){
b.pb(1e9);
b.pb(1e9+1);
b.pb(-1);
}
else if(a[i]==2){
b.pb(1e9);
b.pb(-1);
b.pb(1e9+1);
}
else{
if(ok){
b.pb(1e9);
b.pb(1e9+1);
b.pb(1.5);
}
else{
b.pb(1e9);
b.pb(-1);
b.pb(1e9+1);
b.pb(-2);
}
}
c=b;
sort(c.begin(),c.end());
int sz=(int)b.size();
for(int j=0;j<sz;j++){
b[j]=lower_bound(c.begin(),c.end(),b[j])-c.begin();
}
}
for(auto x:b){
ans.pb(x);
}
return ans;
}
