//In the name of God
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 5001;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll a[maxn], b[maxn], c[maxn];
bool ok[maxn];
void exploreCave(int n) {
for(ll i = 0; i < n; i++){
for(ll j = 0; j < n; j++){
b[j] = a[j];
}
ll x = tryCombination(b);
if(x == -1) x = n;
ll l = -1, r = n - 1, mid;
ll m2 = 0;
while(r - l > 1){
mid = (l + r) >> 1;
if(m2 < mid){
while(m2 <= mid){
if(!ok[m2]) b[m2] ^= 1;
m2++;
}
}
else{
while(m2 - 1 > mid){
m2--;
if(!ok[m2]) b[m2] ^= 1;
}
}
m2 = mid;
ll y = tryCombination(b);
if(y == -1) y = n;
if((x == i) == (y == i)) l = mid;
else r = mid;
}
c[r] = i;
ok[r] = 1;
if(x == i) a[r] = 1;
}
answer(c, a);
}
/*int main(){
fast_io;
return 0;
}*/
