#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
void discretise(vector<int> &v) {
map<int, int> mp;
for (int i = 0; i < (int)(v.size()); i++) {
mp[v[i]] = i;
}
int cnt = 0;
for (pair<int, int> cur : mp) {
v[cur.second] = cnt++;
}
}
vector<int> ans;
int multi, take, notake;
void recur(long long k) {
if (k <= 5) {
if (k == 2) ans = {0};
if (k == 3) ans = {multi++, 0};
if (k == 4) ans = {0, multi++};
if (k == 5) ans = {multi++, multi++, 0};
return;
}
if (k & 1) {
recur((k - 3) / 2);
ans.push_back(take--);
ans.push_back(multi++);
} else {
recur((k - 2) / 2);
ans.push_back(multi++);
ans.push_back(take--);
}
}
vector<int> construct_permutation(long long k) {
ans.clear();
multi = 1000;
take = 999;
notake = -1;
recur(k);
discretise(ans);
return ans;
}
