#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=105;
ll add(ll a, ll b)
{
a+=b;
if(a>=2e18) return 2e18;
return a;
}
ll mul(ll a, ll b)
{
if(2e18/a<b) return 2e18;
return a*b;
}
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r)
{
return l+mt()*mt()%(r-l+1);
}
ll dp[100000], pre[100000], suf[100000];
vector<int> zip(vector<int> ve)
{
vector<int> rar=ve;
sort(rar.begin(), rar.end());
for(int i = 0; i < ve.size(); i++)
ve[i]=lower_bound(rar.begin(), rar.end(), ve[i])-rar.begin();
return ve;
}
ll cal(vector<int> ve)
{
ll sum=1;
for(int i = 0; i < ve.size(); i++)
dp[i]=0;
for(int i = 0; i < ve.size(); i++)
{
dp[i]=1;
for(int j = 0; j < i; j++)
if(ve[j]<ve[i])
dp[i]=add(dp[i], dp[j]);
sum=add(sum, dp[i]);
}
return sum;
}
vector<int> construct_permutation(ll k)
{
// if(k<=90)
// {
// vector<int> res;
// res.clear();
// for(int i = k-2; i >= 0; i--)
// res.emplace_back(i);
// return res;
// }
int lim=120;
ll cur=1;
vector<int> ve, sus;
while(true)
{
int len=200;
cur=1;
vector<int> ha;
ha.clear();
for(int i = 0; i < len; i++)
ha.emplace_back(i);
//shuffle(ha.begin()+65, ha.begin()+85, mt);
int Q=15;
while(Q--){
int i = get(1,len-1);
swap(ha[i],ha[i-1]);
}
ve.clear();
for(int i = 0; i < len; i++)
{
pair<ll, int> best={-1, -1};
cur=cal(ve);
if(cur==k) break;
pre[0]=1;
for(int j = 0; j < ve.size(); j++)
{
if(j>0) pre[j]=pre[j-1];
if(ve[j]<ha[i]) pre[j]=add(pre[j], dp[j]);
}
suf[ve.size()]=1;
for(int j = ve.size()-1; j >= 0; j--)
{
suf[j]=suf[j+1];
if(ve[j]>ha[i]) suf[j]=add(suf[j], dp[j]);
}
for(int j = 0; j <= ve.size(); j++)
{
ll tmp;
if(j==0) tmp=suf[j];
else tmp=mul(pre[j-1], suf[j]);
ll nxt=add(cur, tmp);
if(nxt<=k)
{
if(best.se==-1 || best.fi<nxt)
best={nxt, j};
}
}
if(best.se==-1) continue;
ve.insert(ve.begin()+best.se, ha[i]);
cur=best.fi;
if(cur==k) break;
}
// cerr<<cur<<' ';
// for(int x:ve) cerr<<x<<' ';
// cerr<<'\n';
if(cur==k) return zip(ve);
}
assert(0);
}
// int main()
// {
// vector<int> ve=construct_permutation(1000000000000000000);
// cout<<cal(ve)<<'\n';
// for(int x:ve) cout<<x<<' ';
// // for(int k = 2; k <= 90; k++)
// // {
// // vector<int> ve=construct_permutation(k);
// // if(cal(ve)!=k) return cout<<k, 0;
// // cerr<<k<<'\n';
// // }
// }
