#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
vector<int> went, p;
void solve_add(int l, int r, string &s) {
if (l == r) {
return;
}
int mid = (l + r) / 2;
for(int i = mid + 1; i <= r; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i = l; i <= mid; i++) {
s[i] = '1';
}
if(r - l + 1 > 2) {
solve_add(mid + 1, r, s);
}
for(int i = l; i <= mid; i++) {
s[i] = '0';
}
for(int i = mid + 1; i <= r; i++) {
s[i] = '1';
}
if(r - l + 1 > 2) {
solve_add(l, mid, s);
}
for(int i = mid + 1; i <= r; i++) {
s[i] = '0';
}
}
void solve_check(int l, int r, string &s, vector<int> pots) {
// printf("l = %d r = %d\n", l, r);
// for(auto x : pots) {
// printf("%d ", x);
// }
// puts("");
if(l == r) {
// printf("l = %d sz = %d st = %d\n", l, (int) pots.size(), pots[0]);
went[l] = pots[0];
p[pots[0]] = l;
return;
}
int mid = (l + r) / 2;
vector<int> from_left, from_right;
// printf("will check = %d\n", (int) pots.size());
for(auto i : pots) {
s[i] = '1';
if(check_element(s)) {
from_right.push_back(i);
}
else {
from_left.push_back(i);
}
s[i] = '0';
}
for(auto i : from_left) {
s[i] = '1';
}
solve_check(mid + 1, r, s, from_right);
for(auto i : from_left) {
s[i] = '0';
}
for(auto i : from_right) {
s[i] = '1';
}
solve_check(l, mid, s, from_left);
for(auto i : from_right) {
s[i] = '0';
}
}
vector<int> restore_permutation(int n, int w, int r) {
string s(n, '0');
solve_add(0, n - 1, s);
compile_set();
vector<int> pots;
for(int i = 0; i < n; i++) {
pots.push_back(i);
}
went.resize(n);
p.resize(n);
solve_check(0, n - 1, s, pots);
return p;
}
