#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
#include "messy.h"
using namespace std;
void add_interval(int l, int r, int n) {
if(r - l == 1) return;
string s(n, '0');
for(int i{0}; i < l; ++i) s[i] = '1';
for(int i{r}; i < n; ++i) s[i] = '1';
int m{(l + r) >> 1};
for(int i{l}; i < m; ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
add_interval(l, m, n);
add_interval(m, r, n);
}
vector<int> p;
void solve_interval(int l, int r, int n, string s) {
if(r - l == 1) {
for(int i{}; i < n; ++i)
if(s[i] == '0')
p[i] = l;
return;
}
vector<int> in, out;
for(int i{}; i < n; ++i) {
if(s[i] == '0') {
s[i] = '1';
if(check_element(s)) in.push_back(i);
else out.push_back(i);
s[i] = '0';
}
}
for(int i: out) s[i] = '1';
solve_interval(l, (l + r) >> 1, n, s);
for(int i: out) s[i] = '0';
for(int i: in) s[i] = '1';
solve_interval((l + r) >> 1, r, n, s);
}
vector<int> restore_permutation(int n, int, int) {
p.resize(n);
add_interval(0, n, n);
compile_set();
solve_interval(0, n, n, string(n, '0'));
return p;
}
