#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
vector <int> construct_permutation(long long k) {
vector <int> ret;
int firstBit;
for (ll i = 60; i >= 0; i--) {
if ((1ll << i) & k) {
firstBit = i;
break;
}
}
vector <int> v;
for (int i = firstBit - 1; i >= 0; i--) {
if ((1ll << i) & k) {
v.push_back(0);
v.push_back(1);
}
else {
v.push_back(0);
}
}
reverse(v.begin(), v.end());
for (auto e : v) ret.push_back(0);
int numb = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i] == 0) {
ret[i] = numb;
numb++;
}
}
for (int i = v.size() - 1; i >= 0; i--) {
if (v[i] == 1) {
ret[i] = numb;
numb++;
}
}
return ret;
}
//int countWays(vector <int> v) {
// vector <int> dp;
// for (auto e : v) dp.push_back(0);
//
// dp[0] = 0;
// for (int i = 0; i < v.size(); i++) {
// dp[i] = 1;
//
// for (int j = i - 1; j >= 0; j--) {
// if (v[i] > v[j]) {
// dp[i] = dp[j] * 2;
// break;
// }
// }
// }
//
// int ret = 1;
// for (auto e : dp) ret += e;
//
// return ret;
//}
//
//int main() {
// int t;
//
// cin >> t;
// while (t--) {
// int x; cin >> x;
// for (auto e : construct_permutation(x)) cout << e << " "; cout << " - sol\n";
// cout << countWays(construct_permutation(x)) << "\n";
// cout << "\n";
// }
//
// return 0;
//}
