#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(a) begin(a), end(a)
vector<int> construct_permutation(ll n)
{
vector<double> v; v.clear();
vector<int> A,D; A.clear(); D.clear();
while(n>0) D.pb(n%4),n/=4;
reverse(all(D));
int cnt = 0; int tot=0, lol=1, xd = -1;
double ll = 1.95;
for(auto u : D){
if(!cnt){
if(u==2) v.pb(0),tot=1;
else if(u==3) v.pb(1), v.pb(0),tot=2, lol=1;
cnt = 1;
}
else{
if(u==0) v.pb(tot++), v.pb(tot++);
else if(u==1) v.pb(tot++), v.pb(tot++), v.pb(xd--);
else if(u==2) v.pb(tot++), v.pb(xd--), v.pb(tot++);
else if(lol) v.pb(tot++), v.pb(tot++), v.pb(ll), ll-=0.05;
else v.pb(tot++), v.pb(xd--), v.pb(tot++), v.pb(xd--), lol=1;
}
}
auto w = v; sort(all(w));
for(auto u : v) A.pb(lower_bound(all(w),u)-begin(w));
return A;
}
