#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
using namespace std;
vector<int> construct_permutation(long long x) {
int msb = 60;
while ((1LL << msb) > x) msb--;
vector<int> a(2*msb);
int v = 1;
for (int i = 0; i < msb; i++) {
a[2*i] = v++;
}
v = -1e8;
long long pow2 = 1;
for (int j = 2*msb - 1; j >= 0; j -= 2) {
if (x & pow2) a[j] = v++;
pow2 <<= 1;
}
vector<int> b;
for (int i : a) if (i != 0) b.push_back(i);
map<int,int> ind;
for (int i = 0; i < b.size(); i++) ind[b[i]] = i;
v = 0;
for (auto [p, q] : ind) {
b[q++] = v++;
}
return b;
}
