#include "perm.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<signed> construct_permutation(long long k){
k-=2;
vector<int> sm(1000,0);
vector<signed> v;
sm[0]=1;
v.push_back(0);
int x=1;
while(k>0){
bool ok=1;
for (int i = sz(v)/2; i>=0; i--)
{
int s=1;
for (int j = 0; j < i; j++)
{
if(v[j]<x) s+=sm[j];
}
if(s<=k){
sm[x]+=s;
v.insert(v.begin() + i, x);
k-=s;
ok=0;
break;
}
}
x++;
}
return v;
}
