//OccDreamer
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO {
	int len = 0;
	char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++) 
	#define reg register 
	inline int read() { 
		reg char ch = gh(); reg int x = 0; reg char t = 0; 
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh(); 
		while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh(); 
		return t ? -x : x; 
	} 
	inline void putc(char ch) { out[len++] = ch; } 
	template <class T> inline void write(T x) { if (x < 0) putc('-'), x = -x; if (x > 9) write(x / 10); out[len++] = x % 10 + 48; } 
	inline void flush() { fwrite(out, 1, len, stdout); len=0;} 
}using namespace IO;

inline void sprint(int x){write(x); putc(32); flush();}
inline void eprint(int x){write(x); putc(10); flush();}

const int MAXN = 5e5+5;
const int mod = 998244353;

int aa[MAXN], bb[MAXN], cc[MAXN], dd[MAXN];
int de[MAXN], lg[MAXN], S[2], T[2], val[MAXN];
int n, q, a[MAXN], tot, y[MAXN], anc[22][MAXN], cur=1, Q[MAXN<<2], qcnt;
int tree[MAXN], root[MAXN], pos[MAXN], lc[MAXN*21], rc[MAXN*21], sum[MAXN*21], all[MAXN<<2];

struct Query{
	int x, rk, id;
	inline bool friend operator < (const Query &x, const Query &y){
		return x.x<y.x;
	}
}qq[MAXN<<2];

inline int lowbit(int x) {
	return x & -x;
}
inline void add(int x, int v) {
	while(x<=n+1) tree[x]+=v, x+=lowbit(x);
}
inline int ask(int x) {
	int s=0;
	while(x) s+=tree[x], x^=lowbit(x);
	return s;
}

inline void build(int &now, int pre, int l, int r, int pos, int v) {
	now=++tot;
	lc[now]=lc[pre];
	rc[now]=rc[pre];
	sum[now]=sum[pre]+1;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(pos<=mid) build(lc[now],lc[pre],l,mid,pos,v);
	else build(rc[now],rc[pre],mid+1,r,pos,v);
	return ;
}

inline int ask(int now, int l, int r, int rk) {
	if(rk==0 || rk>sum[now]) return 0;
	int mid;
	while(l!=r) {
		mid=(l+r)>>1;
		if(sum[lc[now]]>=rk) now=lc[now], r=mid;
		else rk-=sum[lc[now]], l=mid+1, now=rc[now];
	}
	return l;
}

inline int F(int X, int Y) {
	int s=a[ask(root[X-1],1,n,X-Y)];
	int t=a[ask(root[X-1],1,n,X-Y+1)];
	return max(s,t);
}

inline int FA(int X, int Y) {
	if(y[X]==Y) return X;
	return F(X,Y);
}

inline int fa(int x) {
	if(x==1) return 0;
	int X=x, Y=y[x];
	return F(X,Y);
}

inline void prework() {
	for(int i=1; i<=n; ++i) {
		int x=a[i];
		int u=x-ask(x);
		y[x]=u;
		add(a[i]+1,1);
	}
	int A, B;
	for(int i=1; i<=n; ++i) {
		val[i]=ask(root[i-1],1,n,i-y[i]+1);
		if(i==1) anc[0][i]=0;
		else {
			A=a[ask(root[i-1],1,n,i-y[i])];
			B=a[val[i]];
			anc[0][i]=max(A,B);
		}
		de[i]=de[anc[0][i]]+1;
	}
	for(int i=1; i<=21; ++i)
		for(int j=1; j<=n; ++j) anc[i][j]=anc[i-1][anc[i-1][j]];
	return ;
}

inline bool Anc(int a, int b, int c, int d) {
	return ask(root[a-1],1,n,a-b+1)==ask(root[c-1],1,n,c-d+1);
}

inline PI Solve(int a, int b, int c, int d) {
	S[0]=Q[cur++];
	S[1]=Q[cur++];
	T[0]=Q[cur++];
	T[1]=Q[cur++];
	int A, B;
	if(y[a]==b) A=a;
	else A=max(::a[S[0]],::a[S[1]]);
	if(y[c]==d) B=c;
	else B=max(::a[T[0]],::a[T[1]]);
	if(A==B) {
		if(S[0]==T[0]) {
			if(a>c) return mk(c,d);
			return mk(a,b);
		}
		return mk(A,y[A]);
	}
	if(de[A]>de[B]) swap(A,B), swap(a,c), swap(b,d), swap(S[0],T[0]), swap(S[1],T[1]);
	for(int i=lg[de[B]-de[A]]; i>=0; --i)
		if(de[anc[i][B]]>de[A]) B=anc[i][B];
	if(A==anc[0][B] && S[0]==ask(root[B-1],1,n,B-y[B]+1)) return mk(a,b);
	if(de[B]>de[A]) B=anc[0][B];
	if(A==B) return mk(A,y[A]);
	for(int i=lg[de[A]]; i>=0; --i)
		if(anc[i][A]!=anc[i][B]) A=anc[i][A], B=anc[i][B];
	A=anc[0][A];
	return mk(A,y[A]);
}

inline void Add(int x){
	int l=1, r=n, mid, p=1;
	while(l!=r){
		all[p]++;
		mid=(l+r)>>1;
		if(x<=mid) r=mid, p=p<<1;
		else p=p<<1|1, l=mid+1;
	}
	all[p]++;
	return ;
}

inline int Ask(int rk){
	int l=1, r=n, mid, p=1;	
	if(rk==0 || rk>all[1]) return 0;
	while(l!=r) {
		mid=(l+r)>>1;
		if(all[p<<1]>=rk) p=p<<1, r=mid;
		else rk-=all[p<<1], l=mid+1, p=p<<1|1;
	}
	return l;
}

signed main() {
	n=read();
	for(int i=2; i<=n+2; ++i) lg[i]=lg[i>>1]+1;
	for(int i=1; i<=n; ++i) a[i]=read(), pos[a[i]]=i;
	for(int i=1; i<=n; ++i) build(root[i],root[i-1],1,n,pos[i],1);
	prework();
	q=read(); int now=1;
	for(int i=1;i<=q;++i) {
		int a, b, c, d;
		a=read()+1, b=read()+1, c=read()+1, d=read()+1;
		aa[i]=a, bb[i]=b, cc[i]=c, dd[i]=d;
		qq[++qcnt]=Query{a-1,a-b+1,now}; ++now;
		qq[++qcnt]=Query{a-1,a-b,now}; ++now;
		qq[++qcnt]=Query{c-1,c-d+1,now}; ++now;
		qq[++qcnt]=Query{c-1,c-d,now}; ++now;
	}
	sort(qq+1,qq+1+qcnt); now=1;
	for(int i=1;i<=n+1;++i){
		while(now<=qcnt && qq[now].x==i-1){
			Q[qq[now].id]=Ask(qq[now].rk);
			++now;	
		}
		if(i!=n+1) Add(pos[i]);
	}
	for(int i=1;i<=q;++i){
		PI ans=Solve(aa[i],bb[i],cc[i],dd[i]);
		sprint(ans.fi-1), eprint(ans.se-1);	
	}
	return 0;
}