#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> ans;
void build(int left = 0, int right = n - 1, string cur = string(n, '0')) {
if (left == right)
return;
int m = (left + right) / 2;
for (int i = left; i <= m; ++i) {
cur[i] = 1;
add_element(cur);
cur[i] = 0;
}
cur = string(n, '0');
for (int i = m + 1; i <= right; ++i)
cur[i] = 1;
build(left, m, cur);
cur = string(n, '0');
for (int i = left; i <= m; ++i)
cur[i] = 1;
build(m + 1, right, cur);
}
void find(int left = 0, int right = n - 1, vector<int> pos = ans, string cur = string(n, '0')) {
if (left == right) {
ans[pos[0]] = left;
return;
}
vector<int> l, r;
int m = (left + right) / 2;
for (auto x : pos) {
cur[x] = 1;
if (check_element(cur))
l.emplace_back(x);
else
r.emplace_back(x);
cur[x] = 0;
}
cur = string(n, '0');
for (auto x : r)
cur[x] = 1;
find(left, m, l, cur);
cur = string(n, '0');
for (auto x : l)
cur[x] = 1;
find(m + 1, right, r, cur);
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
ans.resize(n);
build();
compile_set();
iota(ans.begin(), ans.end(), 0);
find();
return ans;
}
