#include<bits/stdc++.h>
#include "perm.h"
using namespace std;
vector <int> solve(long long k){
if(k == 1) return {};
if(k%2 == 0){
vector <int> ans = solve(k/2);
ans.push_back(ans.size());
return ans;
}
vector <int> ans = solve(k-1);
for(auto &x : ans){
x++;
}
ans.push_back(0);
return ans;
}
vector <int> merge(vector <int> a, vector <int> b){
int tam = b.size();
for(auto &x : a){
x += tam;
}
for(auto x : b){
a.push_back(x);
}
return a;
}
vector <int> ssolve(long long k){
vector <int> v = solve(k);
for(int i = 1;i <= min(k-1, 1010LL);i++){
long long x = rand() % k;
long long y = rand() % k;
long long t = x*y;
t %= k;
if(t == 0) t++;
vector <int> aux = merge(solve(t), solve(k-t+1));
if(aux.size()< v.size()) v = aux;
}
return v;
}
vector<int> construct_permutation(long long k){
srand(time(0));
vector <int> ans = ssolve(k);
return ans;
}
