#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long count_inc(const vector<int>& v) {
vector<long long> dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
dp[x+1] = min(dp[x+1],(ll)1e18+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,(ll)1e18+1);
}
return result;
}
vector<int> construct_permutation(long long k)
{
ll kk = k;
vector <int> res;
ll len = log2(k);
vector <int> a;
for (int i=1; i<=len; i++) a.push_back(i-1);
k-=(1LL<<len);
while (k>0)
{
ll it = 0;
while ((1LL<<(it+1))<= k)
{
it++;
}
k-= (1LL<<it);
a.push_back(it);
}
int n=a.size();
vector <int> d(n+1,0);
for (int i=0; i<n; i++) d[a[i]] ++;
for (int i=1; i<=n; i++) d[i]+=d[i-1];
res.resize(n);
for (int i=0; i<n; i++) res[i] = --d[a[i]];
// for (int i:a) cerr<<i<<' '; cerr<<endl;
// for (int i:res) cerr<<i<<' '; cerr<<endl;
vector <int> v=res;
sort(v.begin(),v.end());
for (int i=0; i<n; i++) assert(v[i]==i);
ll ttemp = count_inc(res);
assert(ttemp==kk);
return res;
}
