#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
const int N = 4e5 + 123;
struct query {
int La, Ra, Lb, Rb, id;
} qq[N];
struct qwe{
int k, id, Lb, Rb;
};
vector <qwe> qe[N];
int n, m, q, S[N], E[N], L[N], R[N], Pmin[N], Pmax[N], p[N], sz[N], val[N];
int rootL[N], rootR[N], tinm[N], toutm[N], tin[N], tout[N], timer = 0, tmn[N], tmx[N];
int t[4 * N], to[N], a1[N];
vector <int> Qmin[N], Qmax[N], g[N], gmin[N], gmax[N];
void make_set() {
for (int i = 0; i < n; i++) {
sz[i] = 1;
val[i] = p[i] = i;
}
}
int getp(int u) {
if (u == p[u])
return u;
p[u] = getp(p[u]);
return p[u];
}
void un(int u, int v, bool is =0) {
u = getp(u);
v = getp(v);
if (u == v)
return;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
if (is)
val[v] = max(val[v], val[u]);
else
val[v] = min(val[v], val[u]);
}
void dfsmax(int u, int p=-1) {
tinm[u] = ++timer;
tmx[timer] = u;
for (int i = 0; i < gmax[u].size(); i++)
if (gmax[u][i] != p)
dfsmax(gmax[u][i], u);
toutm[u] = timer;
}
void dfsmin(int u, int p=-1) {
tin[u] = ++timer;
tmn[timer] = u;
for (int i = 0; i < gmin[u].size(); i++)
if (gmin[u][i] != p)
dfsmin(gmin[u][i], u);
tout[u] = timer;
}
void build(int v, int tl, int tr) {
t[v] = 0;
if (tl == tr)
return;
int tm = (tl + tr)>>1;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
}
void upd(int v, int tl, int tr, int pos) {
if (tl == tr) {
t[v] = 1;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm)
upd(v * 2, tl, tm, pos);
else
upd(v * 2 + 1, tm + 1, tr, pos);
t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int tl, int tr, int l, int r) {
if (r < tl || tr < l)
return 0;
int tm = (tl + tr) / 2;
if (l <= tl && tr <= r)
return t[v];
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}
vector<int> check_validity(int n1, vector<int> X, vector<int> Y, vector<int> S1, vector<int> E1, vector<int> L1, vector<int> R1) {
n = n1;
m = X.size();
q = S1.size();
for (int i = 0; i < q; i++) {
S[i] = S1[i];
E[i] = E1[i];
L[i] = L1[i];
R[i] = R1[i];
}
for (int i = 0; i < q; i++) {
Qmin[L[i]].pb(i);
Qmax[R[i]].pb(i);
}
for (int i = 0; i < m; i++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
make_set();
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < g[i].size(); j++) {
if (getp(i) == getp(g[i][j]) || g[i][j] < i)
continue;
Pmin[val[getp(g[i][j])]] = i;
un(i, g[i][j]);
}
for (int j = 0; j < Qmin[i].size(); j++) {
int v = getp(S[Qmin[i][j]]);
rootL[Qmin[i][j]] = val[v];
}
}
make_set();
for (int i = 0; i < n; i++) {
for (int j = 0; j < g[i].size(); j++) {
if (getp(i) == getp(g[i][j]) || g[i][j] > i)
continue;
Pmax[val[getp(g[i][j])]] = i;
un(i, g[i][j], 1);
}
for (int j = 0; j < Qmax[i].size(); j++) {
int v = getp(E[Qmax[i][j]]);
rootR[Qmax[i][j]] = val[v];
}
}
Pmax[n - 1] = Pmin[0] = -1;
for (int i = 0; i < n; i++) {
if (i != 0) {
gmin[i].pb(Pmin[i]);
gmin[Pmin[i]].pb(i);
}
if (i != n - 1) {
gmax[i].pb(Pmax[i]);
gmax[Pmax[i]].pb(i);
}
}
timer = 0;
dfsmin(0);
timer = 0;
dfsmax(n - 1);
for (int i = 1; i <= n; i++)
a1[tmx[i]] = i;
for (int i = 1; i <= n; i++)
to[i] = a1[tmn[i]];
for (int i = 0; i < q; i++) {
qq[i].id = i;
qq[i].La = tin[rootL[i]];
qq[i].Ra = tout[rootL[i]];
qq[i].Lb = tinm[rootR[i]];
qq[i].Rb = toutm[rootR[i]];
qwe tmp;
tmp.Lb = qq[i].Lb;
tmp.Rb = qq[i].Rb;
tmp.k = 1;
tmp.id = i;
qe[qq[i].Ra].pb(tmp);
tmp.Lb = qq[i].Lb;
tmp.Rb = qq[i].Rb;
tmp.k = -1;
tmp.id = i;
qe[qq[i].La - 1].pb(tmp);
}
vector <int> ans;
ans.clear();
for (int i = 0; i < q; i++)
ans.pb(0);
build(1, 1, n);
for (int i = 1; i <= n; i++) {
upd(1, 1, n, to[i]);
for (int j = 0; j < qe[i].size(); j++) {
qwe tmp = qe[i][j];
ans[tmp.id] += tmp.k * get(1, 1, n, tmp.Lb, tmp.Rb);
}
}
for (int i = 0; i < q; i++)
if (ans[i] != 0)
ans[i] = 1;
return ans;
}
