#include <bits/stdc++.h>
#include "perm.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define sln cout << "\n";
#define sz(x) (int)(x.size())
#define s second
#define ld long double
#define f first
#define pt complex <ld>
#define cyes cout << "YES\n";
#define cno cout << "NO\n";
#define bitcount __builtin_popcountll
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#pragma comment (linker, "/stack:200000")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unswitch-loops")
#pragma GCC target ("avx2")
//#pragma GCC optimize("O3, unroll-loops, Ofast")
//#pragma GCC target("avx, avx2, fma")
//#pragma GCC optimize("no-exceptions")
//#pragma GCC optimize("no-rtti")
//#pragma GCC optimize("stack-reuse=all")
//#define int ll //__int128_t
#define lll __int128_t
using namespace std;
const ll mod = 1e9 + 7;
ld pi = acos(-1);
ll inf = (ll)1e18;
ll binpow (ll n, ll s) {
n %= mod;
ll t = n;
ll ans = 1LL;
while (s > 0LL) {
if ((s & 1)) {
ans = (ans * t) % mod;
}
t = (t * t) % mod;
s = (s >> 1LL);
}
return ans;
}
int lg (int n) {
return 31 - __builtin_clz(n);
}
ll lcm (ll a, ll b) {
return (a * b / __gcd (a, b));
}
vector <int> construct_permutation(ll k) {
bool f = 0;
k --;
if (k == 0) {
return {1, 0};
}
vector <int> a;
int x = k;
for (int i = 62; i >= 1; i --) {
while (k >= (1LL << i) - 1) {
k -= (1LL << i) - 1;
a.pb (i);
}
}
vector <int> ans;
int sum = 0;
for (auto t : a) {
for (int i = t - 1; i >= 0; i --) ans.insert (ans.begin(), sum + i);
sum += t;
}
if (f) {
ans.insert (ans.begin(), sz(ans) + 1);
ans.insert (ans.begin(), sz(ans) - 1);
}
return ans;
}
/*
()(())
(())()()
g++ grader.cpp problem.cpp -o program.exe -std=c++17
program.exe
-1 1 -1 -1 1 -1
-1 1 -1 1 -1 1 -1 -1
1 0 0 1 0 0 1 0
6 4
1 2 4 3 5 6
1 2 3 4 5 6
((()))()()
*/
