P11979 [KTSC 2021] 射击游戏 / gun
题目背景
本题翻译自 [2021년도 국제정보올림피아드 대표학생 선발고사](https://www.ioikorea.or.kr/archives/ioitst/2021/) 2차 선발고사 [#1 총 쏘기](https://assets.ioikorea.or.kr/ioitst/2021/2/gun/gun_statement.pdf)。
**请注意，你不需要也不应该实现 `main` 函数。具体实现方式见【实现细节】部分。**
**警告：滥用本题评测一次即可封号。**
题目描述
有一款由两名玩家共同参与的在线射击游戏。游戏的目标是在一个虚构的城市中摧毁建筑物。
游戏中，$N$ 座建筑物从左到右排列在水平地面上。建筑物从左到右依次编号为 $1$ 到 $N$。每座建筑物的高度用一个序列 $A_i$（$1 \leq i \leq N$）表示，且 $A_i$ 是 $1$ 到 $N$ 之间互不相同的整数。
两名玩家从所有建筑物左侧的同一位置出发。在时间 $i$（$i \geq 1$）时，两名玩家同时发射一发子弹，子弹从发射位置水平向右飞行。两发子弹的速度相同。玩家可以选择子弹的发射高度 $H$，即从地面到子弹的垂直距离，$H$ 为 $1$ 到 $N + 1$ 之间的整数。两名玩家可以选择相同的发射高度。
如果玩家选择的发射高度为 $H$，则子弹会摧毁满足 $A_i \geq H$ 且未被摧毁的最左侧建筑物。如果没有满足条件的建筑物，则不会发生任何事。如果两名玩家的子弹同时满足条件且目标建筑物相同（由于子弹速度相同），则只有该建筑物会被摧毁。特别地，如果两名玩家的发射高度相同，则始终只有一个建筑物被摧毁。例如，若 $A_1 = 2$，$A_2 = 1$，且两名玩家均选择 $H = 1$，则只有建筑物 $1$ 会被摧毁。
问题的目标是：给定 $N$ 座建筑物的高度，找到摧毁所有建筑物的最短时间 $S$，以及每个时间点两名玩家的子弹发射高度。
### 实现细节
你需要实现以下函数：
```cpp
vector< pair > min_shooting_buildings(vector A)
```
- 该函数仅被调用一次。
- 参数 $A$ 是一个长度为 $N$ 的数组，$A[i]$ 表示建筑物 $i + 1$ 的高度 $A_{i+1}$（$0 \leq i \leq N - 1$）。
- 该函数返回一个长度为 $S$ 的数组 $M$，其中 $S$ 是摧毁所有建筑物的最短时间。数组 $M$ 的每个元素 $(a, b)$ 表示两名玩家的子弹发射高度。
在提交的源代码中，任何地方都不允许调用输入输出函数。
输入格式
示例评分程序的输入格式如下：
- 第 $1$ 行：$N$
- 第 $2$ 行：$A[0] \ A[1] \ \cdots \ A[N - 1]$
输出格式
示例评分程序的输出格式如下：
- 第 $i$ 行（$1 \leq i \leq S$）：函数 `min_shooting_buildings` 返回的数组的第 $i$ 个元素。
注意：示例评分程序可能与实际评分程序不同。
说明/提示
### 约束条件
- $1 \leq N \leq 100\,000$
- $1 \leq A_i \leq N$（$1 \leq i \leq N$）
- $A_i$（$1 \leq i \leq N$）互不相同。
### 子任务
1. （$17$ 分）
- 不存在 $1 \leq i < j < k \leq N$ 满足 $A_i < A_j < A_k$。
2. （$12$ 分）
- 不存在 $1 \leq i < j < k \leq N$ 满足 $A_i > A_j > A_k$。
3. （$9$ 分）
- $N \leq 4$。
4. （$12$ 分）
- $N \leq 16$。
5. （$31$ 分）
- $N \leq 500$。
6. （$29$ 分）
- $N \leq 7\,500$。
7. （$40$ 分）
- 无额外约束。
### 评分标准
如果函数 `min_shooting_buildings` 返回的数组长度 $S$ 为摧毁所有建筑物的最短时间，且按返回的数组发射子弹能摧毁所有建筑物，则该测试用例视为正确。
### 示例
- 示例 1：$N = 4$，$A = [1, 2, 4, 3]$。
调用函数：
```cpp
min_shooting_buildings([1, 2, 4, 3])`
```
如图 1 所示，若两名玩家按 $(1, 2), (3, 4), (3, 3)$ 发射子弹，可在时间$3$摧毁所有建筑物。
如图 2 所示，若按 $(1, 4), (2, 3)$ 发射子弹，可在时间 $2$ 摧毁所有建筑物。
因此，函数应返回长度为 $2$ 的数组，例如 `[(1, 4), (2, 3)]`。
- 示例 2：$N = 8$，$A = [4, 3, 8, 2, 1, 7, 6, 5]$。
函数应返回长度为 $4$ 的数组，例如 `[(4, 8), (3, 7), (2, 6), (1, 5)]`。
- 示例 3：$N = 8$，$A = [5, 6, 7, 1, 2, 8, 3, 4]$。
函数应返回长度为 $4$ 的数组，例如 `[(5, 6), (7, 8), (1, 2), (3, 4)]`。