#include "bits/stdc++.h"
#include "popa.h"
//#include "grader.cpp"
using namespace std;
vector <int> Left, Right;
int root;
void F(int l, int r, int whom = -1, int flag = 0) {
if(l > r) return;
if(l == r) {
if(flag == -1) Left[whom] = l;
else Right[whom] = l;
return;
}
for(int i = l; i <= r; i ++) {
if(query(i, i, l, r)) {
if(whom == -1) root = i;
else {
if(flag == -1) Left[whom] = i;
else Right[whom] = i;
}
F(l,i-1,i,-1);
F(i+1,r,i,+1);
return;
}
}
assert(false);
// cout << l << " " << r << " " << whom << " " << flag << "\n";
}
int solve(int n, int *L, int *R) {
// query(x, x, x, y) == 1 -> x is parent of y
root = -1;
Left.resize(n,-1);
Right.resize(n,-1);
F(0, n-1);
for(int i = 0; i < n; i ++) L[i] = Left[i];
for(int i = 0; i < n; i ++) R[i] = Right[i];
Left.clear();
Right.clear();
return root;
}
