#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned long long
vector<int> construct_permutation(long long k) {
switch (k) {
case 1:
return {};
case 2:
return {0};
case 3:
return {1, 0};
case 4:
return {2, 1, 0};
default: break;
};
vector<int> a;
switch (k % 4) {
case 0:
case 2:
a = construct_permutation(k / 2);
a.push_back(a.size());
return a;
case 1:
a = construct_permutation(k - 1);
a.insert(a.begin(), a.size());
return a;
case 3:
a = construct_permutation(k - 3);
for (uint x = 0; x < a.size(); x++)
if (a[x] >= 2) a[x]++;
a.push_back(2);
return a;
default: break;
}
return a;
}
