#include <bits/stdc++.h>
using namespace std;
int query(int a, int b, int c, int d);
int solve(int n, int *l, int *r){
vector<int> adj[n];
for(int i=0; i<n; i++){
l[i]=r[i]=-1;
}
stack<int> st;
st.push(0);
for(int i=1; i<n; i++){
int prev=-1;
while(!st.empty()){
int x=query(st.top(),i,i,i);
if(x==0){
break;
}
prev=st.top();
st.pop();
}
if(!st.empty()){
if(prev!=-1) adj[st.top()].pop_back();
adj[st.top()].push_back(i);
}
if(prev!=-1) adj[i].push_back(prev);
st.push(i);
}
for(int i=0; i<n; i++){
for(int j:adj[i]){
if(j<i) l[i]=j;
else r[i]=j;
}
}
while((int)st.size()>1) st.pop();
return st.top();
}
