配点 : 100 点
問題文
时间是 20XX 年,世界是由 Distributed AtC◯der 公司统治的反乌托邦。目前,人们的娱乐活动仅限于以分布式和并行处理为主题的编程竞赛。例如,周末一家人通过 (ssh) 访问超级计算机,这是一种很常见的景象。(参考题目文本: UTPC 2011 题目 A)
(实际上,下面所述的问题设定比起分布式更像是并行处理,与 Distributed Sorting 相比更像是 Parallel Sorting,但用 D 开头的更方便,而且这里也做了自我辩解,总之今天是圣诞节,我们不纠结细节。)
在分布式·并行处理下,即使是看似基础的处理,也常常可以考虑多种多样的优化方法。例如,N 由 不同整数 组成的整数列 X_1, X_2, ..., X_N 考虑对其进行升序排序的处理。
对于排序,我们假设使用具有以下 1 类型操作的机器。
- 操作: 2k 的 您可以创建一个包含不同给定索引 A_1, A_2, ..., A_{2k} 时,对应交换第 i (1 \leq i \leq k)对于 X_{A_{2i-1}} 和 按字典顺序比较 X_{A_{2i}} (X 可以得到第 A_{2i-1} th 和 由于您拿了第 A_{2i} 个值。但当对每个 j (1 \leq j \leq 2k)对于 1 \leq A_j \leq N 。
例如 如果 X = (5, 3, 1, 2, 4) 什么时候 k=2,(A_1, A_2, A_3, A_4) = (1, 3), (2, 4) 进行操作时,X = (1, 2, 5, 3, 4) 。
使用仅此操作 X 所需的操作最小次数以将其按升序排序,并且实际以该最小次数的操作 X 排序步骤输出一个的程序。
制約
- 1 \leq N \leq 10^5.
- 1 \leq X_i \leq 10^9.
- X_i 是各不相同的整数。
入力
输入是按以下格式从标准输入给出的。
N X_1 X_2 ... X_N
出力
1 线 X 输出将其按升序排序所需的最少操作次数,随后输出每次操作的内容 1 每操作 1 请以行的形式输出。
在表示操作的行首输出交换值的对数 k 然后,接着空格 2k 整数 给出了 A_1, A_2, ..., A_{2k} 以空格分隔。
入力例 1
3 2 3 1
出力例 1
2 1 1 3 1 2 3
如果操作次数最少,并且步骤能正确按升序排序,也会被视为正确输出。比如对于这个输入例子
2 1 1 2 1 3 1
这样的输出也会被视为正确。
入力例 2
3 1 2 3
出力例 2
0
入力例 3
5 5 4 3 2 1
出力例 3
1 2 1 5 2 4