# include "cave.h"
# include <bits/stdc++.h>
# define FILE
using namespace std;
/*
int N, S[6000], D[6000];
int call;
int tryCombination( int P[] ){
int mn = 1e9;
call ++;
for( int i = 0; i < N; i ++ ){
if( S[i] != P[i] ){
mn = min( mn, D[i] );
}
}
if( mn == 1e9 )
return -1;
else
return mn;
return 0;
}
void answer( int P[], int C[] ){
cout << "number of calls :" << call << endl;
for( int i = 0; i < N; i ++ )
cout << P[i] << " ";
cout << endl;
for( int i = 0; i < N; i ++ )
cout << C[i] << ' ';
cout << endl;
for( int i = 0; i < N; i ++ ){
if( P[i] != S[i] || C[i] != D[i] ){
cout << "INCORRECT ANSWER" << endl;
exit( 0 );
}
}
cout << "CORRECT ANSWER" << endl;
}
*/
void exploreCave(int N){
int S[N] = {}, D[N] = {};
for( int i = 0; i < N; i ++ )
S[i] = D[i] = -1;
int loc[N] = {};
for( int i = 0; i < N; i ++ ){
for( int i = 0; i < N; i ++ ){
if( S[i] == -1 ){
loc[i] = 0;
}
else{
loc[i] = S[i];
}
}
int open = 0;
int door = tryCombination( loc );
if( door == i ){
open = 1;
for( int i = 0; i < N; i ++ ){
if( S[i] == -1 ){
loc[i] = open;
}else{
loc[i] = S[i];
}
}
}
int l = 0, r = N-1;
while( l != r ){
int m = ( l + r ) >> 1;
for( int i = l; i <= m; i ++ ){
if( S[i] == -1 ){
loc[i] = 1-open;
}else{
loc[i] = S[i];
}
}
int door = tryCombination( loc );
if( door == i ){
r = m;
}else{
l = m+1;
}
for( int i = l; i <= m; i ++ ){
if( S[i] == -1 ){
loc[i] = open;
}else{
loc[i] = S[i];
}
}
}
S[l] = open;
D[l] = i;
}
answer( S, D );
}
/*
int main(){
# ifdef FILE
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
# endif
cin >> N;
for( int i = 0; i < N; i ++ )
cin >> S[i];
for( int i = 0; i < N; i ++ )
cin >> D[i];
exploreCave( N );
}
*/
