#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define gcd __gcd
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ts cin.tie(nullptr)->sync_with_stdio(false);
#define debug cout<<"HI"<<endl;
const int inf = 1e9;
const ll infll = 1e18;
using namespace std;
vector<int> construct_permutation(ll k){
deque<bool> ops;
while(k>1){
if(k%2==0){ ops.push_front(true); k/=2; }
else{ ops.push_front(false); k--; }
}
deque<int> res;
int lo=0, hi=ops.size()-1;
for(auto op:ops){
if(op) res.push_front(hi--);
else res.push_back(lo++);
}
return vector<int>(all(res));
}
// int main(){
// ts
// ll n; cin >> n;
// auto v = construct_permutation(n);
// for(auto &i:v) cout << i << " ";
// return 0;
// }
