#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 6003;
ll fen[MAXN];
int nTree;
void modify(int i, ll v) {
for (++i; i <= nTree; i += i & -i)
fen[i] += v;
}
ll get(int i) {
ll res(0);
for (++i; i > 0; i -= i & -i)
res += fen[i];
return res;
}
ll calc(vector<int> &a) {
ll res(1);
nTree = sz(a) + 1;
for (int i = 1; i <= nTree; ++i)
fen[i] = 0;
for (int it = 0; it < sz(a); ++it) {
ll way = 1 + get(a[it]);
modify(a[it], way);
res += way;
}
return res;
}
vector<int> construct_permutation(ll k) {
/*if(k <= 90) {
vector<int> p;
for (int i = k - 2; i >= 0; --i)
p.push_back(i);
return p;
}*/
vector<int> p;
ll max_sum(0);
int n(0);
while(max_sum < k) {
vector<int> new_p, idt;
bool check(0);
for (int it = 0; it <= sz(p); ++it)
idt.push_back(it);
shuffle(idt.begin(), idt.end(), rng);
for (int x = 0; x < sz(idt); ++x) {
int it(idt[x]);
vector<int> tmp;
for (int jt = 0; jt < it; ++jt)
tmp.push_back(p[jt]);
tmp.push_back(0);
for (int jt = it; jt < sz(p); ++jt)
tmp.push_back(p[jt]);
vector<int> id;
for (int t = 0; t <= n; ++t)
id.push_back(t);
shuffle(id.begin(), id.end(), rng);
for (int z = 0; z < sz(id); ++z) {
int t(id[z]);
tmp[it] = t;
for (int jt = 0; jt < sz(tmp); ++jt) {
if(it != jt && tmp[jt] >= t)
++tmp[jt];
}
ll ans = calc(tmp);
if(ans <= k && max_sum < ans) {
max_sum = ans;
new_p = tmp;
check = 1;
}
if(check && z > 10)
break;
for (int jt = 0; jt < sz(tmp); ++jt) {
if(it != jt && tmp[jt] > t)
--tmp[jt];
}
}
if(check && x > 10)
break;
}
p = new_p;
++n;
}
return p;
--k;
for (int i = 64 - __builtin_clzll(k); i > 0; --i) {
while(k >= (1LL << i) - 1) {
vector<int> t;
for (int j = 0; j < i; ++j)
t.push_back(sz(p) + j);
for (int it = 0; it < sz(p); ++it)
t.push_back(p[it]);
p = t;
k -= (1LL << i) - 1;
}
}
return p;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "perm"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ll k;
cin >> k;
vector<int> a = construct_permutation(k);
cout << "PERM SIZE: " << sz(a) << '\n';
cout << "ANSWER PERM: ";
for (int it = 0; it < sz(a); ++it)
cout << a[it] << ' '; cout << '\n';
cout << "NUM WAY: " << calc(a) << '\n';
return 0;
}
#endif // Nhoksocqt1
