#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
void discretise(vector<int> &v) {
map<int, int> mp;
for (int i = 0; i < (int)(v.size()); i++) {
mp[v[i]] = i;
}
int cnt = 0;
for (pair<int, int> cur : mp) {
v[cur.second] = cnt++;
}
}
vector<int> ans;
int multi, add;
void recur(long long k) {
if (k == 2) {
ans = {0};
return;
} else if (k == 3) {
ans = {multi++, 0};
return;
} else if (k == 7) {
ans = {2, 1, 3, 0};
multi += 3;
return;
}
if (k % 4 == 3) {
recur(k / 4);
ans.push_back(add - 1);
ans.push_back(add);
add -= 2;
ans.push_back(multi++);
} else if (k & 1) {
recur(k - 1);
ans.push_back(add--);
} else {
recur(k / 2);
ans.push_back(multi++);
}
}
void checking(vector<int> &v) {
int n = v.size();
long long dp[n];
long long tot = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (v[j] < v[i]) {
dp[i] += dp[j];
}
}
tot += dp[i];
}
cout << "Total number of subsequences is " << tot << endl;
}
vector<int> construct_permutation(long long k) {
ans.clear();
multi = 1;
add = -1;
recur(k);
discretise(ans);
// cout << "Answer: ";
// for (int &x : ans) cout << x << ' '; cout << endl;
// checking(ans);
return ans;
}
