//#include<game>
#include <iostream>
#include <vector>
#include <cmath>
#include<map>
#include <algorithm>
#include <iomanip>
#include <string>
#include<stack>
#include <set>
#include <queue>
#include <chrono>
#include<array>
#include<bitset>
#include<unordered_map>
#include<random>
#include<cassert>
#include<cstring>
using namespace std;
using ll = long long;
using db = double;
const float pi = 3.14159265359;
#define V vector
#define VI V<int>
#define P pair<int,int>
#define rep(i, a, b, step) for (int i = int(a); i <= int(b); i += step)
#define repl(i,a,b,step) for (int i = int(a); i >= int(b); i -= step)
#define sn << '\n'
#define ed << endl
#define sz size()
#define print cout <<
#define debug(x) cerr<< #x << " = " << x sn;
#define mpII map<int,int>
#define mine min_element
#define maxe max_element
#define all(v) begin(v), end(v)
#define txt freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout)
#define pb push_back
#define pq priority_queue
#define rev reverse
#define nuyn(a) a.erase(unique(all(a)), end(a))
#define nx next_permutation
#define pk pop_back()
#define START print "Start" sn
#define END print "End" sn
#define ff first
#define ss second
#define ts to_string
#define ub upper_bound
#define mk make_pair
#define lb lower_bound
#define testcase int t;cin>>t;while(t--)solution();
deque<int>an;
VI ans;
int n;
void rec(ll k) {
//debug(k);
if (!k)return;
if (k == 1) {
an.push_front(++n);
return;
}
int cnt = 0, mx = 0;
ll K = 0;
repl(i, 60, 0, 1) {
if (k & (1ll << i)) {
mx = i;
repl(j, n + i, n + 1, 1)an.push_front(j);
n += i;
break;
}
}
if ((1ll << mx) == k) {
rec(1);
return;
}
repl(i, mx - 1, 0, 1) {
if (!i) {
if (k & 1) {
if (K & 2)rec(2);
K |= 2;
}
else K |= 1;
}
else if (k & (1ll << i)) {
K |= 1ll << i;
}
}
rec(K);
}
std::vector<int> construct_permutation(long long k)
{
--k;
n = -1;
ans.clear();
an.clear();
rec(k);
for (auto& i : an)ans.pb(i);
//debug(n);
++n;
V<ll>dp(n + 1);
dp[0] = 1;
ll sum = 1;
rep(i, 1, n, 1) {
dp[i] = 1;
rep(j, 1, i - 1, 1)if (ans[j - 1] < ans[i - 1])
dp[i] += dp[j];
sum += dp[i];
}
// debug(sum);
return ans;
}
