#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace {
long long count_increasing_user(const vector<int>& v) {
static long long MX=1e18;
vector<long long> dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
dp[x+1] = min(dp[x+1],MX+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,MX+1);
}
return result;
}
bool first_execution = true;
const int MAX_PERMSIZE = 9, MAX_PREPERM = (1<<MAX_PERMSIZE);
vector<bool> found(MAX_PREPERM);
vector<pair<ll, vector<int>>> perm_precomputed;
vector<vector<int>> access_perm(MAX_PREPERM);
const int MAX_PRETO = 1215640;
vector<int> dp_value(MAX_PRETO+5, (int)1e9);
vector<pair<int, int>> dp_backtrack(MAX_PRETO, {-1, -1}); // 0 = +, 1 = x
void init() {
for (int sz = 1; sz <= MAX_PERMSIZE; sz++) {
vector<int> p(sz);
iota(p.begin(), p.end(), 0);
do {
ll val = count_increasing_user(p);
if (!found[val]) {
perm_precomputed.emplace_back(val, p);
found[val] = true;
}
} while (next_permutation(p.begin(), p.end()));
}
sort(perm_precomputed.begin(), perm_precomputed.end());
for (auto [val, arr] : perm_precomputed)
access_perm[val] = arr;
dp_value[1] = 1;
for (int i = 2; i < MAX_PRETO+5; i++) {
for (int j = 0; j < perm_precomputed.size(); j++) {
int val = perm_precomputed[j].first;
int sz = perm_precomputed[j].second.size();
if (val > i) break;
if (i-val+1 != 1 && dp_value[i-val+1] + sz < dp_value[i]) {
dp_value[i] = dp_value[i-val+1] + sz;
dp_backtrack[i] = {0, val};
}
if (i%val == 0 && dp_value[i/val] + sz < dp_value[i]) {
dp_value[i] = dp_value[i/val] + sz;
dp_backtrack[i] = {1, val};
}
}
}
}
}
vector<int> add(vector<int> a, vector<int> b) {
for (int &i : a) i += b.size();
a.insert(a.end(), b.begin(), b.end());
return a;
}
vector<int> multiply(vector<int> a, vector<int> b) {
for (int &i : b) i += a.size();
a.insert(a.end(), b.begin(), b.end());
return a;
}
vector<int> construct_small(int k) {
vector<int> cur = {};
vector<pair<int, ll>> seq;
while (k > 1) {
auto [op, val] = dp_backtrack[k];
if (op == 0) {
seq.emplace_back(op, val);
k -= val-1;
} else {
seq.emplace_back(op, val);
k /= val;
}
}
reverse(seq.begin(), seq.end());
for (auto [op, val] : seq) {
if (op == 0) {
cur = add(cur, access_perm[val]);
k -= val-1;
} else {
cur = multiply(cur, access_perm[val]);
k /= val;
}
}
return cur;
}
vector<int> construct_permutation(ll k) {
if (first_execution) {
init();
first_execution = false;
}
return construct_small(k);
}
