#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;
int l[maxn], r[maxn], a[maxn];
int solve(int n, int* Left, int* Right){
stack<int> s;
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
for (int i = 0; i < n; i++)
Left[i] = Right[i] = -1;
for (int i = 0; i < n; i++){
while (!s.empty()){
int k = s.top();
if (query(k, i, i, i) == 1){
r[k] = i;
s.pop();
continue;
}
l[i] = k;
break;
}
s.push(i);
}
int root = 0;
for (int i = 0; i < n; i++)
if (l[i] == -1 and r[i] == -1)
root = i;
for (int i = 0; i < n; i++){
if (i == root)
continue;
if (l[i] == -1)
Left[r[i]] = i;
else if (r[i] == -1)
Right[l[i]] = i;
else{
if (r[l[i]] == r[i])
Right[l[i]] = i;
else
Left[r[i]] = i;
}
}
return root;
}
