//chcockolateman
#include<bits/stdc++.h>
using namespace std;
map<long long,long long> calced[130];
long long cost(long long k,long long turn)
{
if(k==0)
return 0;
if(turn > 120)
return 1e9;
if(calced[k][turn])
return calced[k][turn];
long long pos = 0;
while((1ll<<(pos+1)) - 1 <= k)
pos++;
long long new_k = k - ((1ll<<pos) - 1);
long long ret = pos + cost(new_k,turn+1);
if(turn != 1 && k != 1)
{
pos = 0;
while((1ll<<(pos+1)) <= k)
pos++;
new_k = k - (1ll<<pos);
ret = min(ret,pos + cost(new_k,turn+1));
}
calced[k][turn] = ret;
return ret;
}
std::vector<int> construct_permutation(long long k)
{
k--;
long long counter = -1;
vector<long long> seq;
vector<bool> swapped;
long long turn = 0;
while(k)
{
turn++;
long long pos1 = 0;
while((1ll<<(pos1+1)) - 1 <= k)
pos1++;
long long new_k = k - ((1ll<<pos1) - 1);
long long cost_1 = pos1 + cost(new_k,turn + 1);
bool chose_first = true;
long long pos_2 = 0;
if(turn != 1 && k != 1)
{
while((1ll<<(pos_2+1)) <= k)
pos_2++;
new_k = k - (1ll<<pos_2);
long long cost_2 = pos_2 + cost(new_k,turn + 1);
if(cost_2 < cost_1)
{
seq.push_back(pos_2);
counter += pos_2;
swapped.push_back(true);
k -= (1ll<<pos_2);
chose_first = false;
}
}
if(chose_first)
{
seq.push_back(pos1);
counter += pos1;
k -= ((1ll<<pos1) - 1);
swapped.push_back(false);
}
}
vector<int> ret;
for(long long L = 0 ; L < seq.size() ; L++)
{
long long last = ret.size() - 1;
counter = counter - seq[L] + 1;
for(long long i = 1 ; i <= seq[L] ; i++)
ret.push_back(counter++);
counter = counter - seq[L] - 1;
if(swapped[L])
swap(ret[last],ret[last+1]);
}
return ret;
}
