#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e3+3, M = 3e2+2, X = 3e2+2;
const ll L = 62;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> construct_permutation(ll k)
{
vector<int> p;
if (!k) return p;
ll K = k;
k--;
int r = N;
//vector<int> p2;
for (int j = L; j > 0; j--) {
//cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl;
if (k >= (1ll << j) - 1ll) {
k -= (1ll << j) - 1ll;
for (int l = 1; l <= j; l++) {
/*p2*/p.push_back(r-j+l);
}
//cerr << j << endl;
r -= j;
j = L+1;
}
}
/*if (p.empty() || p2.size() < p.size()) swap(p, p2);
}*/
for (int i = 1; i <= M; i++) {
// cojo i subsequences
// he de sumar k+i-1
ll nwK = K + i - 1;
int cnt[L+1];
for (int j = L; j >= 0; j--) {
cnt[j] = (((nwK >> j) & 1) ? 1 : 0);
}
int c = __builtin_popcountl(nwK);
while (c < i) {
bool b = 0;
for (int j = L; j > 0; j--) {
if (cnt[j]) {
cnt[j-1] += 2;
cnt[j]--;
c++;
b = 1;
break;
}
}
if (!b) break;
}
if (c != i) continue;
//cerr << "cojo " << i << endl;
r = N;
vector<int> p2;
for (int j = L; j >= 0; j--) {
while (cnt[j]--) {
for (int l = 1; l <= j; l++) {
p2.push_back(r-j+l);
//cerr << r-j+l << endl;
}
r -= j;
}
}
if (p.empty() || p2.size() < p.size()) swap(p, p2);
}
for (int tt = 0; tt < X; tt++) {
k = K-1;
r = N;
vector<int> p2;
for (int j = L; j > 0; j--) {
//cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl;
if (k >= (1ll << j) - 1ll && rng() % 3 == 2) {
k -= (1ll << j) - 1ll;
for (int l = 1; l <= j; l++) {
p2.push_back(r-j+l);
}
//cerr << j << endl;
r -= j;
j = L+1;
}
if (k && j == 1) j = L+1;
}
if (p.empty() || p2.size() < p.size()) swap(p, p2);
}
int sz = p.size();
for (int i = 0; i < sz; i++) {
p[i] -= N-sz+1;
}
return p;
}
