#include "popa.h"
#include <bits/stdc++.h>
using namespace std;
int par[1005];
int solve(int n,int* lc,int* rc){
for(int i=0;i<n;++i)par[i]=-1,lc[i]=-1,rc[i]=-1;
int cur=0;
for(int i=1;i<n;++i){
//printf("i=%d:\n",i);
while(true){
//printf("cur=%d\n",cur);
if(query(par[cur]+1,i,par[cur]+1,cur)){
if(rc[cur]==-1){
par[i]=cur;
rc[cur]=i;
cur=i;
break;
}
else{
par[rc[cur]]=i;
lc[i]=rc[cur];
rc[cur]=i;
par[i]=cur;
cur=i;
break;
}
}
else{
if(par[cur]==-1){
lc[i]=cur;
par[cur]=i;
cur=i;
break;
}
else cur=par[cur];
}
}
}
while(par[cur]!=-1)cur=par[cur];
return cur;
}
