#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
using ll = long long;
long long fact(int n){
long long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
vector<int> construct_permutation(long long k){
if (k<=120){
vector <int> v;
for (int i=k-2; i>=0; i--){
v.push_back(i);
}
return v;
}
vector <ll> f;
f.push_back(0);
f.push_back(0);
int c=1;
while (f[c]<1e18){
c++;
f.push_back(f[c-1]+fact(c-1));
}
ll cur=118;
vector <int> v;
while (k>120){
for (int i=20; i>=0; i--){
if (k-f[i]>=120){
k=k-f[i];
cur=cur-i+1;
v.push_back(cur);
cur--;
break;
}
}
}
vector <int> vv;
int tt=0,tp=118;
while (tt<v.size()){
for (int i=v[tt]; i<=tp; i++){
vv.push_back(i);
}
tp=v[tt]-1;
tt++;
}
for (int i=tp; i>=0; i--){vv.push_back(i);}
return vv;
}
