#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ans(long long k, int n) {
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
do {
int ind1, ind0;
for (int i = 0; i < n; i++) {
if (ans[i] == 0) ind0 = i;
if (ans[i] == 1) ind1 = i;
}
if (ind1 > ind0) continue;
vector<long long> lans(n, 0);
long long su = 1;
for (long long i = 0; i < n; i++) {
lans[i] = 1;
for (long long j = 0; j < i; j++) {
if (ans[i] > ans[j]) lans[i] += lans[j];
}
su += lans[i];
}
if (su == k) {
return ans;
}
} while (next_permutation(ans.begin(), ans.end()));
return {-1};
}
std::vector<int> construct_permutation(long long k)
{
if (k < 12) {
/*vector<int> lans;
for (int i = 1; i < k; i++) {
lans.push_back(lans.size());
}
reverse(lans.begin(), lans.end());*/
int i = 1;
while (true) {
auto tmp = ans(k, i);
if (tmp[0] != -1) return tmp;
i++;
}
}
vector<int> lans = construct_permutation(k / 4);
lans.push_back(lans.size());
if (k % 4 == 2) {
for (auto &i : lans) i++;
lans.push_back(0);
}
lans.push_back(lans.size());
if (k % 4 == 1) {
for (auto &i : lans) i++;
lans.push_back(0);
}
if (k % 4 == 3) {
for (auto &i : lans) if (i > 1) i++;
lans.push_back(2);
}
return lans;
/*for (int i = 1; i < 90; i++) {
auto tmp = ans(k, i);
if (tmp[0] == -1) continue;
return tmp;
}*/
/*vector<int> p;
long long cur = 1;
for (long long i = 0; (1ll << (i + 1)) <= k; i++) {
cur *= 2;
p.push_back(i);
}
long long n = p.size();
while (k - cur > 0) {
long long x = __lg(k - cur);
for (auto &i : p) {
if (i >= x) i++;
}
p.push_back(x);
cur += (1ll << x);
}
return p;*/
}
