#include <bits/stdc++.h>
#include "cave.h"
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;
void exploreCave(int n) {
int s[n] = {0}, d[n] = {0}, on[n] = {0}, c[n] = {0};
for(int i = 0; i < n; i++) {
int all = tryCombination(s);
if(all != i) {
int l = 0, r = n - 1;
while(l <= r) {
int mid = (l + r) >> 1;
for(int j = 0; j <= mid; j++) {
if(on[j]) continue;
s[j] ^= 1;
}
int cur = tryCombination(s);
if(cur != i) l = mid + 1;
else {
// cout << "yes\n";
r = mid - 1;
c[i] = mid;
}
for(int j = 0; j <= mid; j++) {
if(on[j]) continue;
s[j] ^= 1;
}
}
}
else if(all == i) {
int l = 0, r = n - 1;
while(l <= r) {
int mid = (l + r) >> 1;
for(int j = 0; j <= mid; j++) {
if(on[j]) continue;
s[j] ^= 1;
}
int cur = tryCombination(s);
if(cur == i) l = mid + 1;
else {
r = mid - 1;
c[i] = mid;
}
for(int j = 0; j <= mid; j++) {
if(on[j]) continue;
s[j] ^= 1;
}
}
s[c[i]] ^= 1;
}
d[c[i]] = i;
// cout << "c[i] = " << c[i] << '\n';
on[c[i]] = 1;
}
answer(s, d);
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
