#include "popa.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int solve(int n, int *lft, int *rgt){
for(int x=0;x<n;x++){
lft[x]=rgt[x]=-1;
}
deque<int>d;
d.push_back(0);
for(int x=1;x<n;x++){
while(!d.empty()){
int hold=d.back();
if(query(hold,x,x,x)){
lft[x]=hold;
d.pop_back();
}
else break;
}
if(!d.empty()) rgt[d.back()]=x;
d.push_back(x);
}
return d.front();
}
