#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> construct_permutation(long long k)
{
if (!k) return {};
// cout << "Solving for " << k << endl;
if (k == 2) {
return {0};
} else if (k == 3) {
return {1, 0};
} else if (k == 4) {
return {0, 1};
} else if (k == 5) {
return {1, 2, 0};
}
else if (k == 6) {
return {0, 2, 1};
}
else if (k % 6 == 0) {
vector<int> res = construct_permutation(k/6);
for (auto &x: res) x+=3;
vector<int> a{0, 2, 1};
res.insert(res.begin(), a.begin(), a.end());
return res;
} else {
long long rem = k%6;
vector<int> res = construct_permutation(k - rem);
vector<int> a;
if (rem == 1) {
a = {0};
}
else if (rem == 2) {
a = {1, 0};
} else if (rem == 3) {
a = {0, 1};
} else if (rem == 4) {
a = {1, 2, 0};
} else if (rem == 5) {
a = {0, 2, 1};
}
for (auto &x: a) x += res.size();
res.insert(res.begin(), a.begin(), a.end());
return res;
}
}
