#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "perm.h"
struct ST {
int n;
vector<long long> tr;
ST(int N) {
n = 1;
while (n < N) n <<= 1;
tr.assign(2 * n, 0);
}
void update(int p, ll v) {
p += n;
tr[p] = v;
for (p /= 2; p >= 1; p /= 2) tr[p] = tr[2 * p] + tr[2 * p + 1];
}
ll query(int l, int r) {
ll res = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) res += tr[l++];
if (r & 1) res += tr[--r];
}
return res;
}
};
vl cnt(vi &A) {
int n = A.size();
ST st(n+5);
vl dp(n+1);
dp[0] = 1;
f0r(i, n) {
dp[i+1] = 1+st.query(0, A[i]);
st.update(A[i], dp[i]);
}
fnr(i, 1, n+1) dp[i] += dp[i-1];
return dp;
}
vi construct_permutation(long long k)
{
vi A{0};
k -= 2;
while (k) {
vl c = cnt(A);
int i = A.size()-1;
for (; i >= 0; --i) if (c[i] <= k) {
A.insert(A.begin()+i, A.size());
k -= c[i];
break;
}
}
return A;
/*
int l = __lg(k), x = l;
vi A(l);
iota(all(A), 0);
for (int i = l-1; i >= 0; --i) if ((k >> i) & 1) A.insert(A.begin()+i, x++);
return A;
*/
}
