#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> construct(long long k, int base){
vector <int> v;
multiset <int> s;
for (int i=0;i<base;i++){
v.push_back(0);
s.insert(1);
k--;
}
v.pop_back();
while (k){
int res=-1;
long long sum=0;
for (int i:s){
if (sum+i>k)
break;
sum+=i;
res++;
}
k-=sum;
v.push_back(res);
s.insert(sum);
}
return v;
}
std::vector<int> construct_permutation(long long k)
{
if (k==1)
return {};
if (k==2)
return {0};
int ch[1001];
memset(ch,0,sizeof(ch));
vector <int> v2=construct(k,2);
vector <int> v3=construct(k,3);
vector <int> res;
if (v2.size()>v3.size())
res=v3;
else
res=v2;
for (int i=res.size()-1;i>=0;i--){
int cnt=0;
res[i]++;
while (res[i]){
cnt++;
if (!ch[cnt])
res[i]--;
}
res[i]=cnt-1;
ch[cnt]=1;
}
return res;
}
