#include "perm.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define REP(i,o,n) for(auto i=o;i<n;i++)
using namespace std;
std::vector<int> construct_permutation(long long k)
{
vector<int> vec;
// k++;
REP(i,0,60){
if(k&(1LL<<i))vec.pb(1);
vec.pb(0);
}
while(vec.back()==0)vec.pop_back();
// cerr<<"DATA: ";
// for(auto i:vec)cerr<<i<<" ";
// cerr<<endl;
vec.pop_back();
reverse(vec.begin(),vec.end());
int mn=0,mx=-1;
for(auto&i:vec){
if(i==0)i=++mx;
else i=--mn;
}
// cerr<<"DATA: ";
// for(auto i:vec)cerr<<i<<" ";
// cerr<<endl;
for(auto &i:vec)i-=mn;
// cerr<<"DATA: ";
// for(auto i:vec)cerr<<i<<" ";
// cerr<<endl;
return vec;
}
