#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
int solve(int n, int *left, int *right)
{
int last = 0;
left[last] = right[last] = -1;
vector <int> par(n);
par[last] = -1;
for (int i = 1; i < n; i++)
{
int prv = last;
while (last != -1 && !query(last, i, last, last))
{
prv = last;
last = par[last];
}
if (last == -1)
{
par[i] = -1;
par[prv] = i;
left[i] = prv;
right[i] = -1;
}
else
{
if (right[last] == -1)
{
right[last] = i;
left[i] = -1;
right[i] = -1;
par[i] = last;
}
else
{
left[i] = right[last];
par[left[i]] = i;
right[i] = -1;
right[last] = i;
par[i] = last;
}
}
last = i;
}
while (par[last] != -1)
last = par[last];
return last;
}
