#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
vector<int> parent;
vector<bool> seen;
int cntr;
void calc(int v, int p) {
while (v != p) {
seen[v] = true;
cntr = max(cntr, v);
bool ok = true;
for (int i = p + 1; i <= v; i++)
ok &= seen[i];
if (ok) {
parent[v] = p;
calc(v + 1, v);
}
else {
if (query(v, v + 1, v + 1, v + 1))
parent[v] = v + 1;
else {
calc(v + 1, v);
parent[v] = cntr + 1;
}
}
v = parent[v];
}
}
int solve(int N, int* L, int* R) {
cntr = 0;
parent.assign(N, -1);
seen.assign(N, false);
calc(0, N);
for (int i = 0; i < N; i++)
L[i] = R[i] = -1;
int r = -1;
for (int i = 0; i < N; i++) {
if (parent[i] == -1)
r = i;
else {
if (i < parent[i])
L[parent[i]] = i;
else
R[parent[i]] = i;
}
}
return r;
}
