#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> construct_permutation(long long k)
{
vector<int> ans, num(91,1);
int minn=-1,maxn=0,skip=2,c2=0;
long long tmp=k;
while(tmp>1){
if(tmp%2){
c2++;
}
tmp/=2;
}
while(k>1){
while(!num[maxn]) maxn++;
if(k%2==0){
ans.push_back(minn);
minn--;
k/=2;
} else if(k%4==3&&c2>=4){
ans.push_back(skip);
num[skip]=0;
skip++;
c2-=2;
k-=3;
} else{
ans.push_back(maxn);
maxn++;
skip++;
c2--;
k--;
}
}
int total=ans.size();
for(int i=0;i<total;i++){
if(ans[i]<0)ans[i]=total+ans[i];
}
reverse(ans.begin(),ans.end());
return ans;
}
