#include "perm.h"
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef long long ll;
vi construct_permutation(long long k){
k--;
if(k == 0) return {};
if(k == 1) return {0};
if(k == 2) return {1, 0};
if(k % 5 == 4){
vi st = construct_permutation((k - 4) / 5 + 1);
st.PB((int)st.size() + 1);
st.PB((int)st.size() + 1);
st.PB((int)st.size() - 1);
return st;
}
if(k % 4 == 3){
vi st = construct_permutation((k - 3) / 4 + 1);
st.PB((int)st.size());
st.PB((int)st.size());
return st;
}
if(k % 3 == 2){
vi st = construct_permutation((k - 2) / 3 + 1);
st.PB((int)st.size() + 1);
st.PB((int)st.size() - 1);
return st;
}
vi st = construct_permutation((k - 1) / 2 + 1);
st.PB((int)st.size());
if(!(k & 1)){
for(int& x : st) x++;
st.PB(0);
}
return st;
}
