#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
const int MAXN = 5e3 + 5;
int ktory[MAXN];
int good[MAXN];
int query(int a, int b, int kt, int n){
int q[n];
for(int i = 0; i < n; ++i){
if(good[i] != -1){
q[i] = good[i];
}
else{
if(i >= a and i <= b){
q[i] = kt;
}
else{
q[i] = (kt ^ 1);
}
}
}
return tryCombination(q);
}
void obl(int i, int n){
int q[n];
for(int i = 0; i < n; ++i){
if(good[i] != -1){
q[i] = good[i];
}
else{
q[i] = 0;
}
}
int j = tryCombination(q);
int kt;
if(j > i or j == -1){
kt = 0;
}
else{
kt = 1;
}
//cout << kt << "\n";
int p = 0;
int k = n - 1;
int x, y;
while(p != k){
int sr = (p + k) / 2;
//cout << p << " " << sr << " " << kt << "\n";
for(int i = p; i <= k; ++i){
if(good[i] != -1){
q[i] = good[i];
}
else{
if(i <= sr){
q[i] = kt;
}
else{
q[i] = (kt ^ 1);
}
}
}
int x = tryCombination(q);
if(x > i or x == -1){
k = sr;
}
else{
for(int i = p; i <= k; ++i){
if(good[i] != -1){
q[i] = good[i];
}
else{
if(i <= sr){
q[i] = (kt ^ 1);
}
else{
q[i] = kt;
}
}
}
p = sr + 1;
}
}
//cout << i << " " << p << "\n";
good[p] = kt;
ktory[p] = i;
return;
}
void exploreCave(int n){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < n; ++i){
good[i] = -1;
ktory[i] = -1;
}
for(int i = 0; i < n; ++i){
obl(i, n);
}
int U[n];
int P[n];
for(int i = 0; i < n; ++i){
U[i] = good[i];
P[i] = ktory[i];
}
answer(U, P);
return;
}
