#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
/*
int SS[5000],DD[5000],__N,RR[5000];
int tryCombination(int *P){
cout<<'!';
for(int i=0;i<__N;i++){
cout<<' '<<P[i];
}
cout<<endl;
for(int i=0;i<__N;i++){
if(SS[RR[i]]!=P[RR[i]]){
cout<<i<<endl;
return i;
}
}
cout<<-1<<endl;
return -1;
}
void answer(int *SSS,int *DDD){
for(int i=0;i<__N;i++){
cout<<' '<<SSS[i];
}
cout<<endl;
for(int i=0;i<__N;i++){
cout<<' '<<DDD[i];
}
cout<<endl;
}
*/
int N,S[5000],D[5000],A[5000],T[5000];
void exploreCave(int _N) {
N=_N;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
A[j]=1;
}
for(int j=0;j<i;j++){
A[T[j]]=S[T[j]];
}
int t=tryCombination(A);
if(t==-1||i<t){
//1:open
int L=-1;
int R=N-1;
while(L+1!=R){
int M=(L+R)/2;
for(int j=0;j<=M;j++){
A[j]=1;
}
for(int j=M+1;j<N;j++){
A[j]=0;
}
for(int j=0;j<i;j++){
A[T[j]]=S[T[j]];
}
int t=tryCombination(A);
if(t==-1||i<t){
R=M;
}
else{
L=M;
}
}
T[i]=R;
S[T[i]]=1;
D[R]=i;
}
else{
//0:open
int L=-1;
int R=N-1;
while(L+1!=R){
int M=(L+R)/2;
for(int j=0;j<=M;j++){
A[j]=0;
}
for(int j=M+1;j<N;j++){
A[j]=1;
}
for(int j=0;j<i;j++){
A[T[j]]=S[T[j]];
}
int t=tryCombination(A);
if(t==-1||i<t){
R=M;
}
else{
L=M;
}
}
T[i]=R;
S[T[i]]=0;
D[R]=i;
}
}
answer(S,D);
}
/*
int main(){
cin>>__N;
for(int i=0;i<__N;i++){
cin>>SS[i];
}
for(int i=0;i<__N;i++){
cin>>DD[i];
RR[DD[i]]=i;
}
exploreCave(__N);
}
*/
