#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
int S[MAXN], D[MAXN], B[MAXN]; // 0 up 1 down
int first, M;
void solve(int l, int r){
if(l == r){
S[l] = 1;
int f = tryCombination(S);
if(f == -1) f = M;
if(f < first){
S[l] = 0;
B[l] = 1;
D[l] = f;
}
if(f > first){
B[l] = 1;
D[l] = first;
first = f;
}
else if(f == first){
S[l] = 0;
}
return;
}
int m = (l + r)/2;
solve(l, m);
solve(m + 1, r);
for(int i = l; i <= r; i++){
if(B[i]) continue;
S[i] = 1;
int f = tryCombination(S);
if(f == -1) f = M;
if(f < first){
S[i] = 0;
B[i] = 1;
D[i] = f;
}
if(f > first){
B[i] = 1;
D[i] = first;
first = f;
}
else if(f == first){
S[i] = 0;
}
}
return;
}
void exploreCave(int N){
memset(S, 0, sizeof(S));
memset(B, 0, sizeof(B));
first = tryCombination(S);
if(first == -1) first = N;
M = N;
solve(0, N - 1);
int A[N], B[N];
for(int i = 0; i < N; i++){
A[i] = S[i];
B[i] = D[i];
}
answer(A, B);
}
