#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <chrono>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <valarray>
#include <random>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;
template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b){return b>a?a=b,1:0;}
#include "perm.h"
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(char c) {
return string(1, c);
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353; // modint1000000007;
// typedef vector<mint> vmi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use rng() to get unsigned int
// mt19937_64 for random long longs
int f(ll val) {
if (val == 2) return 1;
if (val == 1) return 0;
if (val % 3 == 0) return 2 + f(val / 3);
if (val % 2 == 0) return 1 + f(val / 2);
return 1 + f(val - 1);
}
const ll inf = 1e18;
static bool check_permutation(vector<int> v)
{
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
if(v[i]!=i) return 0;
return 1;
}
long long count_increasing(const vector<int>& v) {
vector<long long> dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
dp[x+1] = min(dp[x+1],inf+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,inf+1);
}
return result;
}
vi construct_permutation(ll k) {
int ile = f(k);
debug(ile);
vi ans(ile);
int p = 0, q = ile - 1;
int nasSmall = 0, nasBig = ile - 1;
while (true) {
debug(k, p, q, nasSmall, nasBig);
if (k == 2) {
ans[p] = nasSmall;
break;
} else if (k == 1) {
break;
} else if (k % 3 == 0) {
k /= 3;
ans[p++] = nasSmall + 1;
ans[p++] = nasSmall;
nasSmall += 2;
} else if (k % 2 == 0) {
ans[q--] = nasBig--;
k /= 2;
} else {
--k;
ans[p++] = nasBig--;
}
}
return ans;
}
// int main() {
// ios_base::sync_with_stdio(false); cin.tie(0);
// int t;
// // cin >> t;
// // t = 1;
// ll k;
// cin >> k;
// auto ans = construct_permutation(k);
// cout << sz(ans) << endl;
// for (auto a : ans) {
// cout << a << ' ';
// }
// cout << endl;
// assert(count_increasing(ans) == k);
// assert(check_permutation(ans));
// // while (t--) {
// // solve();
// // }
// }
