#include <bits/stdc++.h>
using namespace std;
#include "perm.h"

vector<int> construct_permutation(long long k) {
	k--;
	if (k == 1) {
		return { 0 };
	}
	int num = 2;
	vector<int> arr = { 1,0 };
	vector<int> nums;
	while (k > 0) {
		int dig = k % 4;
		nums.insert(nums.begin(), dig);
		k /= 4;
	}
	auto Add1 = [&]() {arr.insert(arr.begin(), num++); };
	auto Add3 = [&]() {arr.insert(arr.begin() + 2, num++); };
	auto Times2 = [&]() {arr.push_back(num++); };
	if (nums[0] == 1) {
		Add3();
	} else {
		if (nums[0] == 3) {
			Add1();
		}
		if (nums.size() > 1) {
			Times2();
			Times2();
		}
	}
	for (int ind = 1; ind < nums.size(); ind++) {
		if (nums[ind] == 2) {
			Times2();
			Add1();
			Times2();
		} else {
			if (nums[ind] == 1) {
				Add1();
			} else if (nums[ind] == 3) {
				Add3();
			}
			Times2();
			Times2();
		}
	}
	return arr;
}