#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "perm.h"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
mt19937 mrand(20070803);
const int T = 90;
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int cc(ll n) {
	if (n == 0) return 0;
	if (n % 2 == 1) return cc(n / 2) + 1;
	if (n % 3 == 2) return cc((n - 2) / 3) + 2;
	return cc(n - 1) + 1;
}
vector <int> solve(ll n) {
	if (n == 0) return vector <int> {};
	F(i, 1, 5) {
		if (n >= i && (n - i) % (i + 1) == 0) {
			vector <int> ans = solve((n - i) / (i + 1));
			int t = ans.size();
			F(j, 1, i) ans.push_back(t + i - j);
			return ans;
		}
	}
	vector <int> ans = solve(n - 1);
	// int t = ans.size();
	for (int& i: ans) i++;
	ans.push_back(0);
	return ans;
}
// ll dp[1010];
ll t[1010];
int len;
void modify(int x, ll y) {
	for (; x <= len; x += x & -x) t[x] += y;
}
ll query(int x) {
	ll s = 0;
	for (; x; x ^= x & -x) s += t[x];
	return s;
}
ll calc(vector <int> x) {
	len = SZ(x);
	F(i, 1, len) t[i] = 0;
	ll s = 0;
	F(i, 0, SZ(x)) {
		ll w = 1 + query(x[i]);
		// F(j, 0, i - 1) {
		// 	if (x[j] < x[i]) {
		// 		dp[i] += dp[j];
		// 	}
		// }
		s += w;
		modify(x[i] + 1, w);
	}
	return s;
}
std::vector<int> construct_permutation(ll n) {
	n--;
	vector <int> ans;
	// if (n <= 90) {
	// 	F(i, 1, n) ans.push_back(n - i);
	// 	return ans;
	// }
	ans = solve(n);
	// int lim = 1;
	// debug << __builtin_popcount(n) << endl;
	// F(i, 1, 60) {
	// 	// vector <int> t(i);
	// 	// F(j, 1, i) t[j - 1] = j - 1;
	// 	// lim = min(1000, lim * i);
	// 	// do {
	// 	// F(j, 1, lim) {
	// 	// 	shuffle(all(t), mrand);
	// 	// 	ll v = calc(t);
	// 	// 		// debug << v << endl;
	// 	// 	if (n >= v) {
	// 	// 		// debug << v << ' ' << cc(n - v) << ' ' << i << endl;
	// 	// 		// vector <int> w = cc(n - v);
	// 	// 		if (cc(n - v) + i < ans.size()) {
	// 	// 			assert(false);
	// 	// 			vector <int> w = solve(n - v);
	// 	// 			ans.clear();
	// 	// 			for (int j: t) ans.push_back(j + w.size());
	// 	// 			for (int j: w) ans.push_back(j);
	// 	// 			if (ans.size() <= T) break;
	// 	// 		}
	// 	// 	}
	// 	// }
	// 	// } while (next_permutation(all(t)));
	// 	// if (ans.size() <= T) break;
	// 	ll t = n - ((1ll << i) - 1);
	// 	if (t < 0) break;
	// 	// debug << i << endl;
	// 	if (cc(t) + i < ans.size()) {
	// 		// debug << " ! " << cc(t) + i << endl;
	// 		vector <int> w = solve(t);
	// 		ans.clear();
	// 		F(j, 1, i) ans.push_back(j - 1);
	// 		for (int j: w) ans.push_back(j + w.size());
	// 	}
	// }
	return ans;
}