#include "perm.h"
#include <algorithm>
using ll = long long;
using namespace std;
const int MAXVAL = 50001;
vector<int> construct_permutation(ll k) {
int mxlast = MAXVAL;
int mnlast = -1;
vector<int> ans;
while (k > 1) {
if (k % 2 == 0) {
ans.push_back(++mnlast);
k /= 2;
} else if (k % 3 == 0) {
ans.push_back(mnlast + 2);
ans.push_back(mnlast + 1);
k /= 3;
mnlast += 2;
} else if (k % 5 == 0) {
ans.push_back(mnlast + 3);
ans.push_back(mnlast + 1);
ans.push_back(mnlast + 2);
k /= 5;
mnlast += 3;
} else if (k % 23 == 0) {
//2 3 5 1 6 4
ans.push_back(mnlast + 2);
ans.push_back(mnlast + 3);
ans.push_back(mnlast + 5);
ans.push_back(mnlast + 1);
ans.push_back(mnlast + 6);
ans.push_back(mnlast + 4);
k /= 23;
mnlast += 6;
} else {
ans.push_back(--mxlast);
--k;
}
}
vector<int> cmp;
for (auto x : ans)
cmp.push_back(x);
sort(cmp.begin(), cmp.end());
for (auto& x : ans)
x = lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
return ans;
}
