#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SZ=207;
int fen[SZ];
void update(int x,int val) {
while(x<SZ) {
fen[x]+=val;
x+=(x&-x);
}
return ;
}
int query(int x) {
int sum(0);
while(x) {
sum+=fen[x];
x-=(x&-x);
}
return sum;
}
std::vector<int> construct_permutation(long long k)
{
for(int i=0;i<SZ;i++) fen[i]=0;
if(k==2) return {0};
--k;
vector <int> res,seq;
ll cnt(0),v(2),z=k;
int maxi(0);
while(z) {
++cnt;
z>>=1LL;
}
--cnt;
for(int i=1;i<=cnt;i++) update(i,1);
seq.emplace_back(1);
ll Bit=(1LL<<(cnt-1));
bool chx=true;
while(Bit) {
if(chx) {
if(k&Bit) {
if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
else seq.insert(seq.begin(),query(v));
update(v,1);
chx=false;
}
++v;
Bit>>=1LL;
}else {
if(k&Bit && k&(Bit>>1LL)) {
if(v+1>cnt) seq.insert(seq.begin()+2,query(v)+1);
else seq.insert(seq.begin()+2,query(v+1));
update(v+1,1);
}else if(k&Bit) {
if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
else seq.insert(seq.begin(),query(v));
update(v,1);
}else if(k&(Bit>>1LL)) {
if(v+1>cnt) seq.insert(seq.begin(),query(v)+1);
else seq.insert(seq.begin(),query(v+1));
update(v+1,1);
}
v+=2;
Bit>>=2LL;
}
}
for(auto x:seq) maxi=max(maxi,x);
for(int i=2;i<=cnt;i++) maxi=max(maxi,query(i));
res.emplace_back(maxi);
for(auto x:seq) res.emplace_back(x-1);
for(int i=2;i<=cnt;i++) res.emplace_back(query(i)-1);
return res;
}
