套路题，来一个模拟赛上想到的，不考虑虚树的不用动脑子还好写的 $\Theta(n \log n)$ 做法。

显然原题等价于初始一个全 $1$ 的 01 串，每次选一个位置变成 $0$（选的位置构成排列），然后把当前序列插入到 01-trie 中。询问 01-trie 上两个结点的 LCA。

首先每次恰好一个 $1$ 变成 $0$，而叶子结点的坐标 $(x,\,y)$ 意味着恰好有 $x - y$ 个 $0$ 和 $y$ 个 $1$，因此每个叶子结点都唯一对应了一个 01 串（反过来也是一样）。

我们知道 LCA 的性质，当两个点呈祖先后代的时候 LCA 是浅的那个点；另一方面，如果它们不是祖先后代关系，那么我们把某个结点下移到它的子树中也不会改变 LCA。

如果我们每次询问的两个结点都是叶子结点，那很显然就是对两个版本的 01 串询问 LCP，这个主席树上二分很容易就能 $\Theta(\log n)$ 单次回答一次询问。我们不需要哈希来求 LCP，毕竟任意区间永远是后面版本的 $0$ 位置集合包含前面版本的 $0$ 位置集合，所以判断版本区间 $0$ 数量是否相等就能二分了。

问题是怎么将询问结点挂到它的某个叶子上，我们不妨考虑将询问点挂在最后一次经过它的 01 串上（为什么不挂在第一次的那个串上，因为前者代码好写），考虑询问点 $(x,\,y)$ 什么时候被经过，当且仅当当前 01 串的前缀 $[1,\,x]$ 恰好有 $x - y$ 个 $0$。

这里如果你直接主席树二分这个叶子的版本就是 $n \log^2 n$ 的，但是我写的连 $2 \times 10^5$ 都过不去，人啥常熟大这一块。所以我们来考虑单 $\log$ 做法。

考虑换维扫描线，将每个询问点 $(x,\,y)$ 挂到 $x$ 上。我们扫描所有 $x = 1 \dots n$，维护 $[1,\,x]$ 这个前缀上出现过的 $0$ 都在哪些版本出现。以版本为下标维护数据结构，则 $[1,\,x] \to [1,\,x + 1]$ 实际上就是对 $x + 1$ 位置的 $0$ 的修改时的版本 $k$ 进行 $+1$，查询就是查一个最大的前缀和恰好为 $x - y$，这个玩意可以树状数组上二分，时间复杂度显然是 $\Theta(n \log n)$ 的。

还有一个问题，我们要怎么判断两个询问点是否是祖先后代关系，实际很简单，我们直接把它们全部挂到某个叶子上。如果它们是祖先后代关系（不妨假设询问点 $p$ 是询问点 $q$ 的祖先），要么它们挂的叶子是同一个，要么两个不同的叶子在 $p$ 的子树中产生了分叉，而既然产生了分叉，这两个叶子的 LCA 一定比 $p$ 深，特判一下就行。

时间复杂度 $\Theta(n \log n)$，没有任何细节，代码非常好写。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define E(i, u) for (int i = h[u], v = e[h[u]].to; ~i; i = e[i].nxt, v = e[i].to)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mid (l + r >> 1)
using namespace std;
typedef long long int ll;
using ull = unsigned long long int; using ld = double;
using pii = pair<int, int>;
template<typename T> using pq = priority_queue<T>; using pli = pair<ll, int>;
template<typename T> using vec = vector<T>;
constexpr int maxn = 5e5 + 10, maxv = 1e9 + 10, mod = 998244353, V = 1e3; constexpr int inf = 1.05e9;
inline ll ksm(ll a, ll b = mod - 2) { ll ls = 1; while (b) (b & 1) && (ls = ls * a % mod), a = a * a % mod, b >>= 1; return ls; }
inline ll dksm(ll a, ll b, int p) { ll ls = 1; while (b) (b & 1) && (ls = ls * a % p), a = a * a % p, b >>= 1; return ls; }
int gcd(int n, int m) { return !m ? n : gcd(m, n % m); }
int n, p[maxn], rt[maxn], tot;
struct Node { int l, r, v; } t[maxn * 23];
#define ls(x) (t[x].l)
#define rs(x) (t[x].r)
#define w(x) (t[x].v)
void mdf(int l, int r, int v, int p, int& x) {
	x = ++tot; t[x] = t[p]; ++w(x); if (l == r) return;
	v <= mid ? mdf(l, mid, v, ls(p), ls(x)) : mdf(mid + 1, r, v, rs(p), rs(x));
}
inline int lca(int l, int r, int x, int y) {
	if (w(x) == w(y)) return r - l + 1;
	else if (w(x) != w(y) && l == r) return 0;
	if (w(ls(x)) == w(ls(y))) return lca(mid + 1, r, rs(x), rs(y)) + mid - l + 1;
	else return lca(l, mid, ls(x), ls(y));
}
inline int qry(int l, int r, int ql, int qr, int x) {
	if (qr < l || ql > r) return 0;
	if (ql <= l && r <= qr) return w(x); int s = 0;
	if (ql <= mid) s += qry(l, mid, ql, qr, ls(x));
	if (qr > mid) s += qry(mid + 1, r, ql, qr, rs(x));
	return s;
}
vec<pii> g[maxn]; int c[maxn], A[maxn], B[maxn], C[maxn], D[maxn], h[maxn], nw[maxn][2];
inline void add(int x) { while (x <= n) ++c[x], x += x & -x; }
inline int fd(int k) {
	int x = 0, s = 0; // 查询和恰好为 k 的最大位置
	for (int i = 19; i >= 0; i--) {
		int p = x + (1 << i);
		if (p <= n && s + c[p] <= k) x = p, s += c[p];
	}
	return x;
}
void solve() {
	scanf("%d", &n);
	rep(i, 1, n) scanf("%d", &p[i]), mdf(1, n, p[i], rt[i - 1], rt[i]), h[p[i]] = i;
	int Q, a, b, c, d;
	scanf("%d", &Q);
	rep(o, 1, Q) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if (a > c) swap(a, c), swap(b, d); // 确保 (a, b) 不高于 (c, d)
		A[o] = a, B[o] = b, C[o] = c, D[o] = d;
		g[a].pb({ a - b, o }), g[c].pb({ c - d, -o });
	}
	rep(x, 0, n) {
		if (x) add(h[x]);
		for (pii u : g[x]) {
			int k = fd(u.X);
			(u.Y > 0 ? nw[u.Y][0] : nw[-u.Y][1]) = k;
		}
	}
	rep(o, 1, Q) {
		int x = nw[o][0], y = nw[o][1];
		a = A[o], b = B[o], c = C[o], d = D[o];
		if (x == y) printf("%d %d\n", a, b);
		else {
			int k = lca(1, n, rt[x], rt[y]);
			int u = qry(1, n, 1, k, rt[x]); // 有 u 个 0，k - u 个 1
			if (k >= a) printf("%d %d\n", a, b);
			else printf("%d %d\n", k, k - u);
		}
	}
}
int main() {
	solve();
	return 0;
}