[R48D]小球移动 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 根空心柱子排成一排，每根柱子的长度均为 $10^9$。柱子从左到右编号为 $1, 2, \dots, n$。

在每根柱子的最上方有一个小球，初始时第 $i$ 根柱子上方的小球编号为 $i$。由于重力作用，小球会从柱子顶部落向底部。

你可以在相邻的两根柱子之间安装水平轨道。轨道具有以下特性：

1. 每条轨道必须安装在一个特定的高度 $h$（$0 < h < 10^9$），且所有轨道的高度互不相同。
2. 当一个小球在第 $j$ 根柱子下降到高度 $h$ 时，如果该高度有一条连接第 $j$ 根和第 $j+1$ 根柱子的轨道，小球必须顺着轨道移动到另一根柱子中，然后继续下降。
3. 小球从高度 $10^9$ 开始下降，按高度从大到小的顺序依次经过遇到的轨道。

给定一个 $1$ 到 $n$ 的排列 $a = (a_1, a_2, \dots, a_n)$。请构造一种安装轨道的方案，使得最后从第 $i$ 根柱子下方落出的小球编号恰好为 $a_i$。

如果有多种满足条件的方案，输出任意一种。可以证明始终存在至少一种方案满足条件。

格式

输入格式

第一行包含一个整数 $n$，表示柱子的数量。

第二行包含 $n$ 个整数，表示目标排列 $a_1, a_2, \dots, a_n$。

输出格式

第一行输出一个整数 $k$，表示你安装的轨道总数。需满足 $0 \le k \le n^2$。

接下来的 $k$ 行，每行输出两个整数 $h_i$ 和 $p_i$（$0 < h_i < 10^9$，$1 \le p_i < n$），表示在高度 $h_i$ 处，在第 $p_i$ 根和第 $p_i+1$ 根柱子之间安装一条轨道。

样例

样例输入 #1

3
3 1 2

样例输出 #1

2
100 2
50 1

样例解释 #1

小球 $1$ ：一开始在第 $1$ 个管道。

• 经过 50 1 之后，来到了第 $2$ 个管道。

小球 $2$ ：一开始在第 $2$ 个管道。

• 经过 100 2 之后，来到了第 $3$ 个管道。

小球 $3$ ：一开始在第 $3$ 个管道。

• 经过 100 2 之后，来到了第 $2$ 个管道。
• 经过 50 1 之后，来到了第 $1$ 个管道。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$100$
$2$	$80$	$2000$

对于 $100\%$ 的数据：$1 \le n \le 2000$，$a$ 为 $1$ 到 $n$ 的一个排列。

本题输出量较大，请使用较快的输出方式。