#include "perm.h"
std::vector<int> construct_permutation(long long k)
{
// +1->1,2,3,5,4<-*2+1
if(k==1)return {};
if(k==2)return {0};
if(k==3)return {1,0};
if(k==4)return {2,1,0};
std::vector<int> ans;
int m = k%4;
if(m==0||m==2)ans=construct_permutation(k/2),ans.push_back(ans.size());
if(m==1)ans=construct_permutation(k-1),ans.insert(ans.begin(),ans.size());
if(m==3)ans=construct_permutation(k-3);
if(m==3)for(int i=0;i<ans.size();i++)if(ans[i]>=2)ans[i]+=1;
if(m==3)ans.push_back(2);
return ans;
}
