#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define ar array
#define nl '\n'
#include "cave.h"
// #include "grader.c"
const int mxN = 5e3 + 5;
bool is[mxN];
int S[mxN], D[mxN];
void exploreCave(int n) {
auto opens = [&](int got, int trg) {
return got == -1 || got > trg;
};
auto color = [&](int trg) {
int q[n]{};
for(int i = 0; i < n; i++) {
if(is[i]) q[i] = S[i];
}
if(opens(tryCombination(q), trg)) return 0;
else return 1;
};
auto Dnc = [&](auto &&self, int l, int r, int trg, int col) -> void {
if(l == r) {
is[l] = true;
S[l] = col;
D[l] = trg;
return;
}
int q[n];
int m = (l + r) >> 1;
for(int i = 0; i < n; i++) {
if(is[i]) q[i] = S[i];
else if(i >= l && i <= m) q[i] = col;
else q[i] = col ^ 1;
}
if(opens(tryCombination(q), trg)) {
self(self, l, m, trg, col);
} else {
self(self, m + 1, r, trg, col);
}
};
for(int i = 0; i < n; i++) {
Dnc(Dnc, 0, n - 1, i, color(i));
}
answer(S, D);
}
