[AdditionalFile5436.zip](file://AdditionalFile5436.zip?type=additional_file)

#5436. 「OOI 2016 Day 2」蝙蝠侠归来

标签: 传统 | 时间限制: 2500 ms | 内存限制: 256 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2016 Day2 T2 「Бэтмен возвращается / Batman Returns」。

如今的哥谭市由一条街道组成，沿街排列着 $n$ 座摩天大楼。这些大楼从西到东依次编号为 $1$ 到 $n$，其中第 $i$ 座大楼的高度为 $h_i$。

每天傍晚，蝙蝠侠都会在城市上空进行巡逻飞行。他会爬到一座摩天大楼的屋顶，然后从那里滑翔到另一座大楼的屋顶。由于持续的强风，他只能向西方向滑翔，但飞行中几乎不损失高度。因此，他只能从编号为 $q$ 的大楼滑翔到编号为 $p$ 的大楼，前提是 $p < q$ 且 $h_p < h_q$。蝙蝠侠在飞行中操控自如，因此 $p$ 和 $q$ 之间的大楼高度和数量无关紧要。出于对城市犯罪率的担忧，蝙蝠侠会选择合适的 $p$ 和 $q$，使得 $q - p$ 的值尽可能大。

市政府制定了 $m$ 个城市重建计划。根据第 $i$ 个计划，只有编号从 $l_i$ 到 $r_i$（包含两端）的大楼会被保留，其余大楼将被拆除。蝙蝠侠不喜欢不确定性，因此对于每个重建计划，他希望提前知道在剩余城市部分进行巡逻的最佳方式，即找到一对 $p_i$ 和 $q_i$，满足 $l_i \leq p_i < q_i \leq r_i$，$h_{p_i} < h_{q_i}$，且 $q_i - p_i$ 的值最大。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示沿街摩天大楼的数量。

第二行包含 $n$ 个整数 $h_i$ $(1 \leq h_i \leq 200000)$，表示从西到东各摩天大楼的高度。

第三行包含一个整数 $m$ $(1 \leq m \leq 200000)$，表示城市重建计划的数量。

接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i < r_i \leq n)$，表示第 $i$ 个计划中市政府计划保留编号从 $l_i$ 到 $r_i$（包含两端）的大楼。

输出格式

对于每个重建计划，输出两个整数，即最佳的 $p_i$ 和 $q_i$。如果巡逻变得不可能，则输出 -1 -1。

如果存在多个最佳大楼对，可以输出其中任意一对。

样例 1

输入

4
2 3 1 4
2
2 3
1 3

输出

-1 -1
1 2

在第一个样例中：

• 对于第一个查询，仅有的可用大楼对高度为 $3$ 和 $1$，但不满足条件 $3 \geq 1$，因此无解。
• 对于第二个查询，大楼 $1$ 和 $2$ 组成的对满足条件，高度分别为 $2$ 和 $3$。

样例 2

输入

7
5 4 2 4 3 1 5
4
2 6
2 7
1 7
3 7

输出

3 5
2 7
2 7
3 7

在第二个样例中：

• 对于第一个查询，符合条件的大楼对有高度 $2$ 和 $3$，以及 $2$ 和 $4$。第一对距离更大，因此是正确答案。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。