#include <vector>
#include <string>
#include <iostream>
#include "messy.h"
void build(int n, int l, int r) {
if(l == r) return;
int m = (l + r) / 2;
std::string ss(n, '1');
for(int i = l; i <= r; i++) {
ss[i] = '0';
}
for(int i = l; i <= m; i++) {
ss[i] = '1';
add_element(ss);
ss[i] = '0';
}
build(n, l, m); build(n, m+1, r);
}
void work(int n, std::vector<int>& res, std::vector<int> v, int l, int r) {
// std::cerr << l << " " << r << " " << v.size() << "\n";
if(l == r) {
res[v[0]] = l;
return;
}
int m = (l + r) / 2;
std::string ss(n, '1');
for(int i : v) {
ss[i] = '0';
}
std::vector<int> lf, rh;
for(int i : v) {
ss[i] = '1';
if(check_element(ss)) lf.push_back(i);
else rh.push_back(i);
ss[i] = '0';
}
work(n, res, lf, l, m);
work(n, res, rh, m+1, r);
}
std::vector<int> restore_permutation(int n, int w, int r) {
build(n, 0, n-1);
compile_set();
std::vector<int> res(n, 0);
std::vector<int> vec(n);
for(int i = 0; i < n; i++) {
vec[i] = i;
}
work(n, res, vec, 0, n-1);
return res;
}
