#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
//
//static long long MX = 1e18;
//
//static bool check_permutation(vector<int> v)
//{
// sort(v.begin(),v.end());
// for(int i=0;i<v.size();i++)
// if(v[i]!=i) return 0;
// return 1;
//}
//
//long long count_increasing(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],MX+1);
// }
// }
// long long result = 0;
// for (int i = 0; i <= (int)v.size(); i++){
// result += dp[i];
// result = min(result,MX+1);
// }
// return result;
//}
//
vector <int> construct_permutation(ll k) {
int tt = 0;
vector <int> ret;
for (ll i = 59; i >= 0; i--) {
if (k >> i & 1) {
if (!tt) {
tt = 1;
int san = 1;
for (int j = 1; j <= i; ++j) {
ret.pb (san);
san += 100;
}
}
else {
ret.pb (ret[i] - 1);
}
}
}
map <int, int> m;
for (int i : ret) {
m[i] = 1;
}
int bel = 0;
for (auto i : m) {
m[i.ff] = bel++;
}
for (int &i : ret) {
i = m[i];
}
assert ((int)ret.sz <= 117);
return ret;
}
//int main() {
// freopen ("input.txt", "r", stdin);
// int t;
// assert(1 == scanf("%d", &t));
// while(t--)
// {
// long long k;
// assert(1 == scanf("%lld",&k));
// vector<int> ret=construct_permutation(k);
// if(!check_permutation(ret))
// {
// printf("WA: Returned array is not a permutation\n");
// exit(0);
// }
// long long inc=count_increasing(ret);
// if(inc!=k) {
// if(inc==MX+1)
// printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
// else
// printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
// exit(0);
// }
// printf("%d\n",(int)ret.size());
// for(int i=0;i<ret.size();i++)
// {
// printf("%d",ret[i]);
// if(i+1==ret.size())
// printf("\n");
// else
// printf(" ");
// }
// }
// return 0;
//}
