#include "cave.h"
#include <bits/stdc++.h>
// solved by bekagg
#define ll long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 5e3+5;
const int MOD = 1e9+7;
int s[N] , d[N] , us[N] , nn;
bool t;
void build(int tl , int tr , int i){
if (tl == tr){
if (t){
d[tl] = i;
us[tl] = 1;
}
else {
s[tl] = 1 - s[tl];
d[tl] = i;
us[tl] = 1;
}
return;
}
int tm = (tl + tr) / 2;
for (int i = tl; i <= tm; i++){
if (us[i]) continue;
s[i] = 1 - s[i];
}
int pos = tryCombination(s);
pos = (pos == -1 ? nn : pos);
for (int i = tl; i <= tm; i++){
if (us[i]) continue;
s[i] = 1 - s[i];
}
if (t){
if (pos <= i){
build(tl , tm , i);
}
else {
build(tm + 1 , tr , i);
}
}
else {
if (pos > i){
build(tl , tm , i);
}
else {
build(tm + 1 , tr , i);
}
}
}
void exploreCave(int n){
nn = n;
for (int i = 0; i < n; i++){
t = 0;
int pos = tryCombination(s);
pos = (pos == -1 ? n : pos);
if (pos > i) t = 1;
build(0 , n - 1 , i);
}
answer(s , d);
}
