有一个两人参与的在线射击游戏。这个游戏的目标是在废墟城市中摧毁建筑物。
在游戏中，有 $N$ 座建筑物矗立在水平地面上，从左到右排列。建筑物按从左到右的顺序用 $1$ 到 $N$ 的整数编号。每座建筑物距离地面的高度由序列 $A_i$ ($1 \le i \le N$) 表示，给定为 $1$ 到 $N$ 的互不相同的整数。
两名玩家位于所有建筑物左侧的同一位置。在时间 $i (\ge 1)$，两名玩家同时各发射一颗子弹，子弹从发射位置水平向右飞行。两颗子弹的速度相同。玩家通过距离地面的高度 $H$ 来决定子弹的发射高度。$H$ 是一个 $1$ 到 $N+1$ 之间的整数。两名玩家可以选择相同的发射高度。
如果玩家的子弹发射高度为 $H$，则满足 $A_i \ge H$ 的最左侧未被摧毁的建筑物会被该子弹摧毁。如果没有建筑物满足此条件，则什么也不会发生。如果两名玩家发射的子弹满足该条件的建筑物是同一座（因为两颗子弹速度相同），则只有这一座建筑物会被摧毁。特别地，如果两名玩家的发射高度相同，则始终只有一座建筑物被摧毁。例如，若 $A_1 = 2, A_2 = 1$，且起初两名玩家都选择 $H = 1$ 作为发射高度，则这两颗子弹只会摧毁建筑物 $1$。
问题是，给定 $N$ 座建筑物的高度，求出摧毁所有建筑物所需的最短时间，以及在每个时间点两名玩家的子弹发射高度。
实现细节
你需要实现以下函数：
vector< pair<int, int> > min_shooting_buildings(vector<int> A)- 该函数仅会被调用一次。
- 作为参数给出的数组 $A$ 的大小为 $N$。数组的每个元素 $A[i]$ 表示建筑物 $i+1$ 的高度 $A_{i+1}$ ($0 \le i \le N-1$)。
- 该函数应返回一个大小为 $S$ 的数组 $M$，其中 $S$ 是两名玩家摧毁所有建筑物所需的最短时间。数组 $M$ 的每个元素 $(a, b)$ 分别表示第一名和第二名玩家的子弹发射高度。
提交的源代码中不得执行任何输入输出函数。
数据范围
- $1 \le N \le 100\,000$
- $1 \le A_i \le N$ ($1 \le i \le N$)
- $A_i$ ($1 \le i \le N$) 互不相同。
子任务
- (17分) 不存在满足 $1 \le i < j < k \le N$ 且 $A_i < A_j < A_k$ 的三元组 $(i, j, k)$。
- (12分) 不存在满足 $1 \le i < j < k \le N$ 且 $A_i > A_j > A_k$ 的三元组 $(i, j, k)$。
- (9分) $N \le 4$
- (12分) $N \le 16$
- (31分) $N \le 500$
- (29分) $N \le 7\,500$
- (40分) 无额外限制。
评分标准
如果 min_shooting_buildings 函数返回的数组大小等于两名玩家摧毁所有建筑物所需的最短时间 $S$，且按照返回数组中的元素进行射击后所有建筑物均被摧毁，则该测试数据得满分。
样例
考虑 $N = 4$, 参数 $A = [1, 2, 4, 3]$ 的情况。 评测程序调用以下函数：
min_shooting_buildings([1, 2, 4, 3])如图 1 所示，若将两名玩家的子弹发射位置定为 $(1, 2), (3, 4), (3, 3)$，则在时间 3 时所有建筑物被摧毁。
图 1
如图 2 所示，若将两名玩家的子弹发射位置定为 $(1, 4), (2, 3)$，则在时间 2 时所有建筑物被摧毁。
图 2
min_shooting_buildings函数应返回一个大小为 2 的数组，其中一种可能的返回内容为[(1, 4), (2, 3)]。考虑 $N = 8$, 参数 $A = [4, 3, 8, 2, 1, 7, 6, 5]$ 的情况。
min_shooting_buildings函数应返回一个大小为 4 的数组，其中一种可能的返回内容为[(4, 8), (3, 7), (2, 6), (1, 5)]。考虑 $N = 8$, 参数 $A = [5, 6, 7, 1, 2, 8, 3, 4]$ 的情况。
min_shooting_buildings函数应返回一个大小为 4 的数组，其中一种可能的返回内容为[(5, 6), (7, 8), (1, 2), (3, 4)]。
输入格式 1
4 1 2 4 3
输出格式 1
(1, 4) (2, 3)
Sample grader
Sample grader 按以下格式接收输入：
- 第 1 行：$N$
- 第 2 行：$A[0] \ A[1] \ \dots \ A[N-1]$
Sample grader 输出以下内容：
- 第 $i$ 行 ($1 \le i \le S$)：函数
min_shooting_buildings返回的数组的第 $i$ 个元素。
请注意，Sample grader 可能与实际评测时使用的评测程序不同。