P11098 [ROI 2022] 滑梯 (Day 1)
题目描述
翻译自 [ROI 2022 D1T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。
佩奇和她的弟弟乔治来到水上公园。乔治喜欢从滑梯上滑行，这个滑梯可以用三角网格的一部分来描述，其中的顶点是滑梯的节点。在每个节点上，可以选择继续沿着哪个管道前进——向左下或向右下。滑梯从上到下编号，从 $0$ 层开始。在第 $0$ 层，滑梯只有一个节点，在第 $1$ 层有两个节点，在第 $i$ 层有 $i + 1$ 个节点。总共有 $n + 1$ 层。每次从上到下滑都要经过恰好 $n$ 个管道。每个节点都有坐标，用两个数字 $(r, c)$ 表示在第 $r$ 层中从左边开始数的第 $c$ 个节点 ($0 \le c \le r \le n$)。请注意，每层和每层上的节点都是从 $0$ 开始编号的。如果乔治位于节点 $(r, c)$ 并向左下滑，他将进入节点 $(r + 1, c)$，如果他向右下滑，他将进入节点 $(r + 1, c + 1)$。
这是一个有 $5$ 层（$n=4$）的滑梯：
乔治想要从滑坡上滑下 $n + 1$ 次。在每次下滑之前，佩奇会给他一个指令，告诉他如何沿着滑坡滑行。每个指令由恰好 $n$ 个命令组成，要么是“向左下”，要么是“向右下”。乔治根据佩奇的命令从当前节点去往下一个节点。第一条指令只有“向右下”的命令。佩奇懒得想出新的指令，因此相邻两次下滑的指令只有一条命令不同：为了从第 $i$ 条指令得到第 $i + 1$ 条指令，需要将第 $a_i$ 个（不是第 $i$ 个）命令从“向右下”更改为“向左下”。每个命令只会被更改一次。到最后，第 $n+1$ 条指令将只包含“向左下”命令。可以证明，在这 $n+1$ 次下滑中，乔治会经过滑梯的每个节点（但不是每个管道）。
在从水上乐园返回的途中，乔治遇到了以下问题。首先，考虑所有他滑过的管道的集合。给出两个节点的坐标：$(r_1, c_1)$ 和 $(r_2, c_2)$。你需要确定一个节点的坐标 $(r_3, c_3)$，使得从这个节点开始，通过这些他滑过的管道可以访问到节点 $(r_1, c_1)$ 和节点 $(r_2, c_2)$，并且在所有这样的节点中，它是最低的，即 $r_3$ 的值最大。可以证明，这样的节点总是存在且唯一。
乔治有很多个问题，但是因为他已经离开了水上乐园，所以他不能碰这个滑梯。他需要你帮忙回答他的所有问题！
输入格式
第一行给出一个整数 $n$（$1 \le n \le 500 000$）。
在第二行中，给出 $n$ 个整数 $a_1, a_2, \dots, a_n $（$1 \le a_i \le n$），其中 $a_i$ 是第 $i$ 次下滑后将要更改的命令的编号。保证所有的 $a_i$ 都是不同的。
在第三行中给出一个整数 $q $（$1 \le q \le 500 000$），表示乔治的问题数量。
在接下来的 $q$ 行中，每行给出四个整数 $r_{i,1}, c_{i,1}, r_{i,2},c_{i,2} $（$0 \le r_{i,1}, r_{i,2} \le n$，$0 \le c_{i,1} \le r_{i,1}$，$0 \le c_{i,2} \le r_{i,2}$），表示第 $i$ 个问题的两个节点的坐标。
输出格式
输出 $q$ 行，每行输出两个整数 $r_{i,3}$ 和 $c_{i,3}$，作为第 $i$ 个问题的答案的节点坐标。
说明/提示
### 样例解释：
乔治四次滑滑梯的路线是这样的：
所以所有他经过的管道的集合是这样的：
五个问题的答案看图易得。
### 数据范围：
| Subtask | 分值 | $n\le$ | $q\le$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $14$ | $300$ | $300$ | |
| $2$ | $23$ | $3000$ | $3000$ | |
| $3$ | $10$ | $100000$ | $100000$ | 对于所有 $i$，$a_i=i$ |
| $4$ | $13$ | $100000$ | $100000$ | 数组 $a$ 有特殊形式 |
| $5$ | $15$ | $100000$ | $100000$ | |
| $6$ | $14$ | $300000$ | $300000$ | |
| $7$ | $11$ | $500000$ | $500000$ | |
Subtask 4 中，数组 $a$ 形如 $1,2,3,\dots,k,n,n-1,n-2,\dots,k+1$，其中 $0\le k\le n$。