题目背景

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 2차 선발고사 #1 총 쏘기。

警告：滥用本题评测一次即可封号。

题目描述

有一款由两名玩家共同参与的在线射击游戏。游戏的目标是在一个虚构的城市中摧毁建筑物。

游戏中，$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$，以及每个时间点两名玩家的子弹发射高度。

实现细节

你需要实现以下函数：

vector< pair<int, int> > min_shooting_buildings(vector<int> 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$ 个元素。

注意：示例评分程序可能与实际评分程序不同。

4
1 2 4 3

2
1 4
2 3

8
4 3 8 2 1 7 6 5

4
4 8
3 7
2 6
1 5

8
5 6 7 1 2 8 3 4

4
5 6
7 8
1 2
3 4

提示

约束条件

• $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]$。

  调用函数：

  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)]。