← 返回题目列表

AtCoder · xmascon16_d

D. 分布式排序

中文机器翻译题面 查看原题

配点 : 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