#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=2e5+100;
vector<int>v[lim];
int vis1[lim],vis2[lim];
vector<int>a;
int tr[lim];
vector<int>ans;
void dfs(int node,int par){
a.pb(node);
for(int j:v[node]){
if(j==par)continue;
dfs(j,node);
}
}
vector<int>check_validity(int n,vector<int>X,vector<int>Y,vector<int>s,vector<int>e,vector<int>L,vector<int>R){
int m=X.size();
int q=s.size();
ans.resize(q);
for(int i=0;i<m;i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
for(int i=0;i<n;i++){
if(v[i].size()==1){
dfs(i,-1);
break;
}
}
for(int i=0;i<n;i++){
tr[a[i]]=i;
}
auto solve=[&]() -> void {
// cerr<<"beg solve\n";
// for(int i=0;i<n;i++)cerr<<a[i]<<' ';
// cerr<<'\n';
// for(int i=0;i<n;i++){
// cerr<<tr[i]<<' ';
// }
// cerr<<'\n';
vector<int>needansl[n],needansr[n];
for(int i=0;i<q;i++){
if(tr[s[i]]<tr[e[i]]){
needansl[tr[s[i]]].pb(i);
needansr[tr[e[i]]].pb(i);
}
}
int cangol[q],cangor[q];
for(int i=0;i<q;i++){
cangol[i]=INT_MAX;
cangor[i]=INT_MIN;
}
vector<int>st;
for(int i=0;i<n;i++){
while(st.size()&&a[st.back()]<a[i]){
st.pop_back();
}
st.pb(i);
for(int id:needansr[i]){
int l=0,r=st.size()-1;
cangol[id]=0;
while(l<=r){
int mid=l+r>>1;
if(a[st[mid]]>R[id]){
cangol[id]=st[mid]+1;
l=mid+1;
}else{
r=mid-1;
}
}
}
}
st.clear();
for(int i=n-1;0<=i;i--){
while(st.size()&&a[st.back()]>a[i]){
st.pop_back();
}
st.pb(i);
// cerr<<"deb :: ";
// for(int i:st)cerr<<a[i]<<' ';
// cerr<<'\n';
for(int id:needansl[i]){
// cerr<<id<<'\n';
int l=0,r=st.size()-1;
cangor[id]=n-1;
while(l<=r){
int mid=l+r>>1;
// if(id==3){
// cerr<<i<<' '<<a[st[mid]]<<' '<<L[id]<<" are ids\n";
// }
if(a[st[mid]]<L[id]){
cangor[id]=st[mid]-1;
l=mid+1;
}else{
r=mid-1;
}
}
}
}
for(int i=0;i<q;i++){
ans[i]|=cangol[i]<=cangor[i];
// cerr<<i<<" :: "<<cangol[i]<<' '<<cangor[i]<<'\n';
}
// cerr<<'\n';
};
// for(int i=0;i<n;i++){
// cerr<<a[i]<<' ';
// }cerr<<'\n';
solve();
for(int i=0;i<n;i++){
tr[i]=n-tr[i]-1;
}
// cerr<<a.size()<<'\n';
// for(int i=0;i<n;i++){
// cerr<<a[i]<<' ';
// }cerr<<'\n';
reverse(a.begin(),a.end());
// for(int i=0;i<n;i++){
// cerr<<a[i]<<' ';
// }cerr<<'\n';
solve();
return ans;
}
// std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
// std::vector<int> S, std::vector<int> E,
// std::vector<int> L, std::vector<int> R) {
// int Q = S.size();
// std::vector<int> A(Q);
// for (int i = 0; i < Q; ++i) {
// A[i] = 0;
// }
// return A;
// }
