#include "perm.h"
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
int f(ll val) {
if (val == 2) return 1;
if (val == 1) return 0;
if (val % 3 == 0) return 1 + f(val / 3);
if (val % 2 == 0) return 1 + f(val / 2);
return 1 + f(val - 1);
}
vi construct_permutation(ll k) {
int ile = f(k);
vi ans(ile);
int p = 0, q = ile - 1;
int nasSmall = 0, nasBig = ile - 1;
while (k) {
if (k == 2) {
ans[p] = nasSmall;
break;
} else if (k == 1) {
break;
} else if (k % 3 == 0) {
ans[p++] = nasSmall + 1;
ans[p++] = nasSmall;
nasSmall += 2;
} else if (k % 2 == 0) {
ans[q--] = nasBig--;
k /= 2;
} else {
ans[p++] = nasSmall++;
}
}
return ans;
}
