#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;
static long long MX = 1e18;
typedef long long ll;
vector<int> rec(vector<int>& ans, ll k, ll add) {
ll m = floor(log2(k));
int n = k - (pow(2, m));
if (n > 1) rec(ans, n, m+add);
for (int j = 0; j < n; j++) ans.push_back(j + m + add);
reverse(ans.end() + 2 - n, ans.end());
for (int d = 0; d < m; d++) ans.push_back(d);
return ans;
}
ll sum(vector<int>& v) {
ll sum = 0;
for(auto a: v) sum+=a;
return sum;
}
vector<int> pows(ll k) {
vector<int> t;
bool b = false;
while( k > 0 ) {
t.push_back(floor(log2(k)));
k -= pow(2,floor(log2(k)));
if(b == false) b = true;
else if(k>0) k++;
else t.push_back(1);
}
return t;
}
std::vector<int> construct_permutation(long long k)
{
ll m = floor(log2(k));
int n = k - (pow(2, m));
vector<int> ans, chunks = pows(k);
ll len = sum(chunks);
ans.resize(len);
for(int i = 0; i < len; i++) ans[i] = i;
reverse(ans.begin(), ans.end());
int s = len, e = len;
for(auto chunk:chunks) {
s -= chunk;
reverse(ans.begin() + s, ans.begin() + e);
e = s;
}
// vector<int> ans2(len-1+chunks.size()); // we count the empty set in every chunk.
// for(int i = 0; i < chunks.size()-1; i++) ans2[i] = len+chunks.size() - 2 - i;
// for(int i = chunks.size()-1; i < len+chunks.size()-1; i++) ans2[i] = ans[i - chunks.size()+1];
return ans;
}
