P16548 [ICPC 2026 LAC] Booksort

Beatriz 一直很喜欢阅读，于是她决定开一家书店，好让自己整天都能与书为伴。她希望确保书籍摆放得井井有条，以便吸引更多顾客。 书店的一个大书架上，有一排共 $N$ 摞书，从左到右编号为 $1$ 到 $N$。第 $i$ 摞书包含 $A_i$ 本书。Beatriz 希望各摞书的数量呈非递减顺序，即对于 $i = 1, 2, \ldots, N - 1$ 有 $A_i \le A_{i+1}$，这可能需要重新整理这些书。 然而，Beatriz 很懒，实在不想亲自动手整理书籍。于是她请来最好的朋友 Bernardo 帮忙。他们约定：Beatriz 向 Bernardo 发出一系列指令。每条指令中，Beatriz 会指定两摞不同的书 $i$ 和 $j$，Bernardo 则把这 $s = A_i + A_j$ 本书取出来，并将它们尽可能均匀地重新分配。这意味着执行该指令后，这两摞书的本数将按以下方式更新： $$ \begin{aligned} A_i &= \left\lfloor \frac{s}{2} \right\rfloor, \\ A_j &= \left\lceil \frac{s}{2} \right\rceil. \end{aligned} $$ Beatriz 不想让 Bernardo 花费太多时间帮她搬书。她希望得到一个长度不超过 $10^5$ 的指令序列，使得最终达到所期望的非递减顺序。但你知道，Beatriz 并不想自己来决定指令。你能为她准备任意一个合法的指令序列吗？

第一行包含一个整数 $N$（$2 \le N \le 5000$），表示书架上书摞的数量。每摞书用一个从 $1$ 到 $N$ 的不同整数标识。 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$1 \le A_i \le 10^5$），其中 $A_i$ 是第 $i$ 摞书的初始本数。

第一行必须输出一个整数 $k$（$0 \le k \le 10^5$），表示要执行的指令数量。 接下来的 $k$ 行，每行用两个整数 $i$ 和 $j$（$1 \le i, j \le N$ 且 $i \neq j$）描述一条指令，表示将第 $i$ 摞和第 $j$ 摞的书按所述方式重新分配。按答案中出现的顺序执行完所有指令后，书架上的书摞必须呈非递减顺序。 可以证明，在给定约束下总是存在合法答案。如果有多组解，输出其中任意一组即可；不需要最小化 $k$。

**样例 1 解释：** 由于书架初始已经按非递减顺序排好，一个空的指令序列是合法的输出。 **样例 2 解释：** 尽管书架初始已经有序，但该输出是合法的，因为书架在经过不超过 $10^5$ 条指令后仍然有序。不需要最小化指令数量。 **样例 3 解释：** 第一条指令（$i=2, j=1$）将书架从 [$\underline{14}, \underline{7}, 13, 8, 15$] 变为 [$\underline{11}, \underline{10}, 13, 8, 15$]。 第二条指令（$i=1, j=4$）将书架从 [$\underline{11}, 10, 13, \underline{8}, 15$] 变为 [$\underline{9}, 10, 13, \underline{10}, 15$]。 第三条指令（$i=3, j=4$）将书架从 [$9, 10, \underline{13}, \underline{10}, 15$] 变为 [$9, 10, \underline{11}, \underline{12}, 15$]，此时已按非递减顺序排好。 翻译由 DeepSeek V4 Pro 完成