#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define isz(a) (int)(a).size()
const int NM = 1000, MX = 1e9;
const ll LIM = 1e18;
ll dp[NM+5], bit[NM+5];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){
int tmp = rng()%(r-l+1);
if (tmp < 0) tmp += r-l+1;
return l + tmp;
}
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> construct_permutation(ll k){
if (k <= 90){
vector <int> res = {};
for (int i = k-2; i >= 0; i--)
res.push_back(i);
return res;
}
vector <int> p = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
while (calc(p) < k){
int l = 1, r = isz(p), res = 0;
while (l <= r){
int mid = (l+r)/2;
vector <int> p_nxt = p;
for (int &x : p_nxt)
if (x >= mid) x++;
p_nxt.push_back(mid);
if (calc(p_nxt) <= k){
res = mid;
l = mid+1;
}
else r = mid-1;
}
for (int &x : p) if (x >= res) x++;
p.push_back(res);
}
return p;
}
