注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "gun.h"。

题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「총 쏘기」

这是一个两人在线射击游戏，游戏的目标是在废墟城市中摧毁建筑物。游戏中，地平线上从左到右排列着 $N$ 座建筑物。建筑物从左到右依次编号为 $1$ 到 $N$。每座建筑物的高度用序列 $A_{i}$ $(1 \leq i \leq N)$ 表示，并且这些高度是 $1$ 到 $N$ 的不同整数。

两名玩家站在所有建筑物左侧的同一位置。在时间 $i$ $(\geq 1)$ 时，两名玩家同时各发射一颗子弹，子弹从发射位置水平向右飞行。两颗子弹的速度相同。玩家可以选择子弹的发射高度 $H$，$H$ 是一个 $1$ 到 $N+1$ 之间的整数。两名玩家可以选择相同的发射高度。

如果玩家的子弹发射高度为 $H$，则满足 $A_{i} \geq 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] $(0 \leq i \leq N-1)$ 表示第 $i+1$ 座建筑物的高度 $A_{i+1}$。
• 该函数返回一个大小为 $S$ 的数组 M，表示两名玩家摧毁所有建筑物所需的最少时间 $S$。数组 M 的每个元素 $(a, b)$ 表示第一名和第二名玩家的子弹发射高度。

注意，提交的代码中不应包含任何输入输出操作。

样例 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$ 个时间单位内摧毁所有建筑物。

min_shooting_buildings 函数应返回一个大小为 $2$ 的数组，可能的结果之一是 [(1,4),(2,3)]。

样例 2

考虑 $N=8$，参数 $A=[4,3,8,2,1,7,6,5]$ 的情况。

min_shooting_buildings 函数应返回一个大小为 $4$ 的数组，可能的结果之一是 [(4,8),(3,7),(2,6),(1,5)]。

样例 3

考虑 $N=8$，参数 A $=[5,6,7,1,2,8,3,4]$ 的情况。

min_shooting_buildings 函数应返回一个大小为 $4$ 的数组，可能的结果之一是 [(5,6),(7,8),(1,2),(3,4)]。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $1 \leq A_{i} \leq N$ $(1 \leq i \leq N)$
• $A_{i}$ $(1 \leq i \leq N)$ 互不相同。

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$

示例评测程序按以下格式输出：

• 第 $i$ $(1 \leq i \leq S)$ 行：函数 min_shooting_buildings 返回的数组的第 $i$ 个元素。

示例评测程序可能与实际评测程序不同。