#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> construct_permutation(long long k) {
if (k == 1) return {};
// 1. Find the highest bit to build the 'main' increasing sequence
int max_bit = 0;
while ((1LL << (max_bit + 1)) <= k) {
max_bit++;
}
vector<int> res;
// Build the backbone: 0, 1, 2, ..., max_bit-1
// This gives us 2^max_bit subsequences
for (int i = 0; i < max_bit; i++) {
res.push_back(i);
}
// 2. Add the remainder k - 2^max_bit
long long remainder = k - (1LL << max_bit);
// We iterate from the highest possible bit down to 0
// To add 2^i, we insert a value that is 'larger' than the first i elements
// but 'smaller' than the rest.
for (int i = max_bit - 1; i >= 0; i--) {
if ((remainder >> i) & 1) {
res.push_back(i);
}
}
return res;
}
