//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 N, a[maxn], b[maxn], c[maxn], aans[maxn], cans[maxn];
bool ok[maxn], bad[maxn];
/*int tryCombination(int S[]){
fill(bad, bad + N, 0);
for(ll i = 0; i < N; i++){
if(aans[i] != S[i]) bad[cans[i]] = 1;
}
for(ll i = 0; i < N; i++){
if(bad[i]) return i;
}
return -1;
}
void answer(int S[], int D[]){
cout << "answer\n";
for(ll i = 0; i < N; i++){
cout << S[i] << " ";
}
cout << "\n";
for(ll i = 0; i < N; i++){
cout << D[i] << " ";
}
cout << "\n";
}*/
void exploreCave(int n) {
for(ll i = 0; i < n; i++){
//cout << "# " << i << "\n";
for(ll j = 0; j < n; j++){
b[j] = a[j];
}
/*for(ll o = 0; o < n; o++){
cout << b[o] << " ";
}*/
ll x = tryCombination(b);
//cout << " -> " << 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){
// cout << "$ " << m2 << "\n";
if(!ok[m2]) b[m2] ^= 1;
m2++;
}
}
else{
while(m2 - 1 > mid){
m2--;
if(!ok[m2]) b[m2] ^= 1;
}
}
/* cout << "! " << mid << "\n";
for(ll o = 0; o < n; o++){
cout << b[o] << " ";
}*/
ll y = tryCombination(b);
//cout << " -> " << 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(a, c);
}
/*int main(){
freopen("sample.in", "r", stdin);
cin >> N;
for(ll i = 0; i < N; i++){
cin >> aans[i];
cout << aans[i] << " ";
}
cout << "\n";
for(ll i = 0; i < N; i++){
cin >> cans[i];
cout << cans[i] << " ";
}
cout << "\nstart\n";
exploreCave(N);
return 0;
}
*/
