有一个两人参与的在线射击游戏。这个游戏的目标是在废墟城市中摧毁建筑物。

在游戏中，有 $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$) 互不相同。

子任务

1. (17分) 不存在满足 $1 \le i < j < k \le N$ 且 $A_i < A_j < A_k$ 的三元组 $(i, j, k)$。
2. (12分) 不存在满足 $1 \le i < j < k \le N$ 且 $A_i > A_j > A_k$ 的三元组 $(i, j, k)$。
3. (9分) $N \le 4$
4. (12分) $N \le 16$
5. (31分) $N \le 500$
6. (29分) $N \le 7\,500$
7. (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 可能与实际评测时使用的评测程序不同。