#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
const ll inf = 1e8;
void adjust_permutation(vector<int> &v) {
vector<int> a = v;
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
for (auto &x : v) {
x = lower_bound(a.begin(), a.end(), x) - a.begin();
}
}
std::vector<int> construct_permutation(long long k)
{
vector<int> bit;
while (k > 0) {
bit.push_back(k % 4LL);
k /= 4LL;
}
vector<int> v;
if (bit.back() == 2) v.emplace_back(0);
if (bit.back() == 3) v.emplace_back(1), v.emplace_back(0);
for (int i = bit.size() - 2; i >= 0; i--) {
if (bit[i] == 0) {
v.emplace_back(inf);
v.emplace_back(inf + 1);
} else if (bit[i] == 1) {
v.emplace_back(inf);
v.emplace_back(inf + 1);
v.emplace_back(-1);
} else if (bit[i] == 2) {
v.emplace_back(inf);
v.emplace_back(-1);
v.emplace_back(inf + 1);
} else if (bit[i] == 3) {
int p0 = 0, p1 = 1;
for (int i = 0; i < v.size(); i++) {
if (v[i] == 0) p0 = i;
if (v[i] == 1) p1 = i;
}
if (p0 < p1) {
v.emplace_back(inf);
v.emplace_back(-1);
v.emplace_back(inf + 1);
v.emplace_back(-2);
} else if (p0 > p1) {
for (auto &x : v) x = (x << 1);
v.emplace_back(inf);
v.emplace_back(inf + 1);
v.emplace_back(3);
}
}
adjust_permutation(v);
}
//for (auto x : v) cout << x << " ";
return v;
}
