#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "perm.h"
std::vector<int> construct_permutation(long long k)
{
int n=0;
ll K=k;
vector<int> ord;
bool stop=0;
while(K>1){
if(K%2==0){
K/=2;
n++;
ord.push_back(2);
}
else if(K%3==0 && !stop){
K/=3;
n+=2;
ord.push_back(3);
ll KK=K;
int N=n;
while(KK>1){
if(KK%2==0){
KK/=2;
N++;
}
else{
KK--;
N++;
}
}
if(N<=90){
stop=1;
}
}
else{
K--;
n++;
ord.push_back(1);
}
}
reverse(ord.begin(), ord.end());
deque<int> a;
vector<int> ans(n);
int curr_s=0;
int curr_e=n;
for(int i=0; i<ord.size(); i++) if(ord[i]==1) curr_e--;
curr_s=curr_e-1;
for(int i=0; i<ord.size(); i++){
if(ord[i]==1){
a.push_front(curr_e);
curr_e++;
}
else if(ord[i]==2){
a.push_front(curr_s);
curr_s--;
}
else{
a.push_front(curr_s-1);
a.push_front(curr_s);
curr_s-=2;
}
}
for(int i=0; i<n; i++){
ans[i]=a.front();
a.pop_front();
}
return ans;
}
