#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
#include "messy.h"
using namespace std;
#define ll long long
#define ld long double
#define all(x) (x.begin(), x.end())
#define rall(x) (x.rbegin(), x.rend())
#define sz(x) (int)x.size()
int N;
vector<int> answ;
void query(int l, int r) {
if(l == r) {
return;
}
int mid = (l + r) / 2;
string s(N, '1');
for(int i = l; i <= r; i++) {
s[i] = '0';
}
for(int i = l; i <= mid; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
query(l, mid);
query(mid + 1, r);
}
void solve(int l, int r, vector<int> li, string s) {
if(l == r) {
answ[l] = li.front();
return;
}
int mid = (l + r) / 2;
vector<int> left, right;
for(auto i: li) {
s[i] = '1';
if(check_element(s)) {
left.push_back(i);
} else {
right.push_back(i);
}
s[i] = '0';
}
for(auto i: right) {
s[i] = '1';
}
solve(l, mid, left, s);
for(auto i: right) {
s[i] = '0';
}
for(auto i: left) {
s[i] = '1';
}
solve(mid + 1, r, right, s);
for(auto i: left) {
s[i] = '0';
}
}
vector<int> restore_permutation(int n, int w, int r) {
N = n;
query(0, N - 1);
compile_set();
string s(N, '0');
vector<int> left;
for(int i = 0; i < N; i++) {
left.push_back(i);
}
answ.assign(N, 0);
solve(0, N - 1, left, s);
vector<int> ansi(N, 0);
for(int i = 0; i < N; i++) {
ansi[answ[i]] = i;
}
return ansi;
}
