#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> construct_permutation(long long k)
{
vector<int> v;
{
long long tmp=2;
while(tmp<=k) {
v.push_back(v.size());
tmp*=2;
}
k-=tmp/2;
}
cerr << v.size() << endl;
vector<int> add;
vector<long long> b4;
while(k>0) {
b4.push_back(k%4);
k/=4;
}
map<int,int> mp;
for(int i =0;i<(int)b4.size();i++) {
if(b4[i]==0)continue;
else if(b4[i]==1) {
mp[2*i]++;
}
else if(b4[i]==2) {
mp[2*i+1]++;
}
else {
mp[2*i+1]++;
mp[2*i]++;
}
}
for(int i = 0;i<=100;i++) {
int c=mp[i]/2;
mp[i]%=2;
if(mp[i])add.push_back(i);
mp[i+1]+=c;
}
reverse(add.begin(),add.end());
for(int i:add) {
v.insert(v.begin()+i,v.size());
}
return v;
}
