#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define isz(a) (int)(a).size()
const int NM = 90, MX = 1e9;
const ll LIM = 1e18;
ll dp[NM+5], bit[NM+5];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void update(int x, ll val){
while (x <= NM){
bit[x] += val;
x += x & (-x);
}
}
ll get(int x){
ll res = 0;
while (x > 0){
res += bit[x];
x -= x & (-x);
}
return res;
}
ll calc(vector <int> &p){
memset(dp, 0, sizeof(dp));
memset(bit, 0, sizeof(bit));
for (int i = 0; i < isz(p); i++){
dp[i] = 1+get(p[i]);
update(p[i]+1, dp[i]);
}
ll res = 1;
for (int i = 0; i < isz(p); i++) res += dp[i];
return res;
}
vector <int> solve(ll k){
int sz = 1;
while ((1LL<<sz) < k) sz++;
vector <int> p = {}, pbest = {};
ll best = -1;
for (int i = 0; i < sz; i++) p.push_back(i);
for (int iter = 1; iter <= 100 || best == -1; iter++){
shuffle(p.begin(), p.end(), rng);
ll tmp = calc(p);
if (tmp <= k){
if (tmp > best){
best = tmp;
pbest = p;
}
}
}
p = pbest;
while (true){
bool chk = 0;
for (int i = 0; i+1 < sz; i++){
if (p[i] < p[i+1]) continue;
swap(p[i], p[i+1]);
if (calc(p) > k) swap(p[i], p[i+1]);
else chk = 1;
}
if (!chk) break;
}
ll res = calc(p);
if (res == k) return p;
vector <int> q = solve(k-res+1);
for (int &x : p) x += isz(q);
for (int x : q) p.push_back(x);
return p;
}
vector <int> construct_permutation(ll k){
if (k <= 90){
vector <int> res = {};
for (int i = k-2; i >= 0; i--)
res.push_back(i);
return res;
}
return solve(k);
}
