#include "perm.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
void doit(deque<signed>& dq,int k,int& cur) {
if (!k) return;
if (k == 1) {
dq.push_front(cur++);
return;
}
if (k%3 == 2) {
doit(dq,(k-2)/3,cur);
dq.push_back(cur+1);
dq.push_back(cur);
cur+=2;
}
else if (k%2==0) {
doit(dq,k-1,cur);
dq.push_front(cur++);
}
else {
doit(dq,(k-1)/2,cur);
dq.push_back(cur++);
}
}
std::vector<signed> construct_permutation(int k)
{
k--;
deque<signed> dq;
int cur = 0;
doit(dq,k,cur);
return vector<signed>(all(dq));
}
