#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> construct_permutation(ll k)
{
if (k == 1)
return {};
if (k == 2)
return {0};
if (k == 3)
return {1, 0};
vector<int> p = construct_permutation(k / 4);
auto big = [&] {
p.push_back(p.size());
};
auto small = [&] {
for (int &x : p)
x++;
p.push_back(0);
};
if (k % 4 == 0) {
big(), big();
}
if (k % 4 == 1) {
big(), big(), small();
}
if (k % 4 == 2) {
big(), small(), big();
}
if (k % 4 == 3) {
bool ok = false;
for (int x : p) {
if (x == 0)
break;
if (x == 1)
ok = true;
}
if (ok) {
big(), big();
for (int &x : p)
if (x > 1)
x++;
p.push_back(2);
}
else
big(), small(), big(), small();
}
return p;
}
