题目描述

给定一个长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$，其中每个 $p_i$ 均在 $[1,n]$ 内且互不相同。

我们考虑一个三角形网格中的点 $(x,y)$，其中：

$$0\le y\le x\le n.$$

对于一个点 $(x,y)$，定义 $t(x,y)$ 为满足下列条件的最小整数 $t$：

$$\#\{j\mid 1\le j\le t,\\ p_j\le x\}=x-y.$$

特别地，当 $x=y$ 时，有 $t(x,y)=0$。

现在有 $q$ 次询问。每次询问给出两个网格点：

$$(x_1,y_1),\qquad (x_2,y_2).$$

令：

$$T_1=t(x_1,y_1),\qquad T_2=t(x_2,y_2).$$

定义：

$$X=\min\left(x_1,x_2,\min_{\min(T_1,T_2)<j\le \max(T_1,T_2)}(p_j-1)\right).$$

若上式中的区间为空，则忽略区间最小值这一项。

再定义：

$$Y=X-\#\{j\mid 1\le j\le T_1,\\ p_j\le X\}.$$

请对每次询问输出点 $(X,Y)$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示一个 $1\sim n$ 的排列。

第三行一个整数 $q$。

接下来 $q$ 行，每行四个整数：

x1 y1 x2 y2

表示一次询问的两个点 $(x_1,y_1)$ 与 $(x_2,y_2)$。

输出格式

输出 $q$ 行。对于每次询问，输出两个整数 $X,Y$，中间用一个空格隔开。

样例

3
2 3 1
5
3 3 3 0
2 2 2 1
1 0 3 1
3 1 3 2
2 2 2 2

0 0
1 1
0 0
2 1
2 2

数据范围与约定

对于全部测试数据：

• $1\le n\le 500000$；
• $1\le q\le 500000$；
• $p_1,p_2,\ldots,p_n$ 是 $1\sim n$ 的排列；
• 对于每个询问，$0\le y_1\le x_1\le n$，$0\le y_2\le x_2\le n$。

说明

本题坐标采用题面中的零基网格坐标，因此输出中可能出现 $0$。