#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 = 5e5+5;
const int MOD = 1e9+7;
int d[N] , cnt , us[N] , s[N] , p , nn;
void build(int tl , int tr){
for (int i = tl; i <= tr; i++){
if (us[i]) continue;
s[i] = 1 - s[i];
}
int pos = tryCombination(s);
if (pos == -1) pos = nn;
int tm = (tl + tr) / 2;
if (pos >= p){
return;
}
else {
for (int i = tl; i <= tr; i++){
if (us[i]) continue;
s[i] = 1 - s[i];
}
if (tl == tr){
if (us[tl] == 0){
us[tl] = 1;
cnt++;
}
}
else {
build(tl , tm) , build(tm + 1 , tr);
}
}
}
void exploreCave(int n){
for (int i = 0; i < n; i++) s[i] = i % 2;
nn = n;
while(cnt < n){
p = tryCombination(s);
if (p == -1) p = n;
build(0 , n - 1);
}
for (int i = 0; i < n; i++){
s[i] = 1 - s[i];
int pos = tryCombination(s);
d[i] = pos;
s[i] = 1 - s[i];
}
answer(s , d);
}
