#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p;
void adds(int L, int R) {
if (L == R) return;
string guess(n,'1');
int mid = (L+R)/2;
for (int i = L; i <= R; i++) guess[i] = '0';
for (int i = L; i <= mid; i++) {
guess[i] = '1';
add_element(guess);
guess[i] = '0';
}
adds(L,mid);
adds(mid+1,R);
}
void checks(int L, int R, vector<int> go) {
int k = go.size();
assert(k == R-L+1);
if (k == 1) {
p[go[0]] = L;
return;
}
int mid = (L+R)/2;
string check(n,'1');
for (int i: go) check[i] = '0';
vector<int> goL, goR;
for (int i: go) {
check[i] = '1';
if (check_element(check)) goL.push_back(i);
else goR.push_back(i);
check[i] = '0';
}
// for (int e: goL) cout << e << " "; cout << "\n";
checks(L,mid,goL);
checks(mid+1,R,goR);
}
std::vector<int> restore_permutation(int nt, int w, int r) {
n = nt;
p.resize(n,-1);
adds(0,n-1);
compile_set();
vector<int> go0(n);
iota(go0.begin(),go0.end(),0);
checks(0,n-1,go0);
return p;
}
