#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 };
	auto Add1 = [&]() {arr.insert(arr.begin(), num++); };
	auto Add3 = [&]() {arr.insert(arr.begin() + 2, num++); };
	auto Times2Plus1 = [&]() {arr.push_back(num++); };
	vector<function<void()>> ops;
	while (k > 4) {
		if (k % 2 == 0) {
			long long  r1 = (k - 3) / 2;
			if (r1 % 2 == 0) {
				ops.push_back(Add1);
				k--;
			} else {
				ops.push_back(Add3);
				k -= 3;
			}
		} else {
			ops.push_back(Times2Plus1);
			k /= 2;
		}

	}
	while (k > 2) {
		ops.push_back(Add1);
		k--;
	}
	for (int i = ops.size() - 1; i >= 0; i--) {
		ops[i]();
	}
	return arr;
}