//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"
#include "popa.h"
using namespace std;
struct Node {
int p, l, r;
};
int solve(int N, int* Left, int* Right) {
vector<Node> no(N, {-1,-1,-1});
for (int i = 1; i < N; ++i) {
int nowN = i - 1;
int last = nowN;
while (query(nowN, i, nowN, nowN) == 0) {
last = nowN;
nowN = no[nowN].p;
if (nowN == -1) break;
}
if (nowN == -1) {
no[last].p = i;
no[i].l = last;
} else {
no[i].p =nowN;
no[i].l = no[nowN].r;
no[nowN].r = i;
}
}
for (int i = 0; i < N; ++i) {
Left[i] = no[i].l;
Right[i] = no[i].r;
}
int ro = 0;
while (no[ro].p != -1) ro = no[ro].p;
return ro;
}
