#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=200050;
const int L=19;
struct DSU
{
int p[N];
void init(){ for(int i=0;i<N;i++) p[i]=i;}
DSU(){ init();}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
struct BIT
{
int sum[N];
void init(){ for(int i=0;i<N;i++) sum[i]=0;}
BIT(){ init();}
void Add(int i, int f){ for(;i<N;i+=i&-i) sum[i]+=f;}
int Get(int i){ int ret=0;for(;i;i-=i&-i) ret+=sum[i];return ret;}
int Get(int l, int r){ return Get(r)-Get(l-1);}
} BT;
struct Tree
{
vector<int> E[N];
int par[N][L],dep[N],root,nod[N],lid[N],rid[N],tid;
Tree(){}
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
void SetRoot(int u){ root=u;}
void DFS(int u, int p)
{
lid[u]=++tid;
nod[tid]=u;
par[u][0]=p;
dep[u]=dep[p]+1;
//printf("%i ",u);
for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
for(int v:E[u]) if(v!=p) DFS(v,u);
//printf("%i ",u);
rid[u]=tid;
}
void DFS(){ DFS(root,0);}//printf("\n");}
int UpLo(int u, int x)
{
for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]<=x) u=par[u][i];
return u;
}
int UpHi(int u, int x)
{
for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]>=x) u=par[u][i];
return u;
}
} Lree,Rree;
struct Query
{
int l,r,mul,id;
Query(int b=0, int c=0, int e=0, int f=0){ l=b,r=c,mul=e,id=f;}
};
int sol[N];
struct QuerySolver
{
int a[N],b[N],id[N],n;
vector<Query> Qs[N];
QuerySolver(){}
void init(int v[], int u[], int sz)
{
n=sz;
for(int i=1;i<=n;i++) a[i]=v[i],b[i]=u[i];
for(int i=1;i<=n;i++) id[b[i]]=i;
}
void AddQuery(int s, int e, int l, int r, int idex)
{
Qs[s-1].pb(Query(l,r,-1,idex));
Qs[e].pb(Query(l,r,1,idex));
}
void Solve()
{
for(int i=1;i<=n;i++)
{
BT.Add(id[a[i]],1);
for(Query my:Qs[i])
{
sol[my.id]+=my.mul*BT.Get(my.l,my.r);
}
}
}
} Solver;
vector<int> E[N];
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(),q=s.size();
for(int i=0;i<m;i++) x[i]++,y[i]++;
for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
for(int i=0;i<m;i++) x[i]++,y[i]++;
for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
n+=2;
for(int i=2;i<=n;i++) E[1].pb(i);
for(int i=1;i<n;i++) E[n].pb(i);
for(int i=0;i<m;i++) E[x[i]].pb(y[i]),E[y[i]].pb(x[i]);
DS.init();
for(int i=1;i<=n;i++) for(int j:E[i]) if(j<i && DS.Find(i)!=DS.Find(j)) Lree.AddEdge(DS.Find(j),i),DS.Union(j,i);
DS.init();
for(int i=n;i>=1;i--) for(int j:E[i]) if(j>i && DS.Find(i)!=DS.Find(j)) Rree.AddEdge(DS.Find(j),i),DS.Union(j,i);
Lree.SetRoot(n);Rree.SetRoot(1);
Lree.DFS();Rree.DFS();
//for(int i=1;i<=n;i++) printf("%i ",Lree.nod[i]);printf("\n");
//for(int i=1;i<=n;i++) printf("%i ",Rree.nod[i]);printf("\n");
BT.init();
Solver.init(Lree.nod,Rree.nod,n);
for(int i=0;i<q;i++)
{
int u=Rree.UpHi(s[i],l[i]);
int v=Lree.UpLo(e[i],r[i]);
Solver.AddQuery(Lree.lid[v],Lree.rid[v],Rree.lid[u],Rree.rid[u],i);
}
vector<int> ret;
Solver.Solve();
for(int i=0;i<q;i++) ret.pb(sol[i]>0);
return ret;
}
/*int read_int(){ int x;scanf("%i",&x);return x;}
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
