#include<bits/stdc++.h>
#include "popa.h"
using namespace std;
#define taskname ""
int solve(int N, int *Left, int *Right) {
for (int i = 0; i < N; i++) {
Left[i] = Right[i] = -1;
}
vector<int> st(1, 0);
for (int i = 1; i < N; i++) {
int y = -1;
while (!st.empty()) {
int x = st.back();
while (~Left[x]) {
x = Left[x];
}
if (query(st.back(), st.back(), x, i)) {
break;
}
y = st.back(); st.pop_back();
}
if (!st.empty()) {
Right[st.back()] = i;
}
Left[i] = y;
st.push_back(i);
}
while (st.size() > 1) {
st.pop_back();
}
return st.back();
}
