#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "perm.h"
#define ll long long
using namespace std;
std::vector<int> construct_permutation(long long k){
vector<int> ans, v, dop;
deque<vector<int>> d;
for(ll i = 62; i >= 0; i--){
if(k >= (1ll << i)){
k -= (1ll << i);
v.push_back(i);
}
}
// cout << v.size() << " " << k << " " << v[0] << "\n";
ll dl = int(v.size()) - 1;
ll pos = 0;
while(!v.empty()){
int num = v.back();
vector<int> res;
for(int i = pos; i < pos + num; i++)
res.push_back(i);
v.pop_back();
d.push_front(res);
pos += num;
}
for(int i = pos + dl - 1; i >= pos; i--)
dop.push_back(i);
d.push_front(dop);
for(auto to : d){
for(int j : to)
ans.push_back(j);
}
return ans;
}
// int main(){
// ll n;
// cin >> n;
// vector<int> res = construct_permutation(n);
// for(int to : res)
// cout << to << " ";
// }
