3360. 多边形排序

单点时限: 1.5 sec

内存限制: 256 MB

章鱼哥在 EOJ 中加入了万众期待的 Polygon 系统,这个系统最大的特色就是可以快速对题目的顺序进行批量交换。Polygon 中只提供了一种交换操作,对于一个长度为 $n$ 题目序列 $a_1, a_2, \ldots, a_n$,你可以任意选取 $b_1, b_2, \ldots, b_k$ $(2 \leq k \leq n, 1 \leq b_i \leq n)$ 且 $b_1, b_2, \ldots, b_k$ 互不相等,但大小顺序任意,在进行交换操作时,系统对 $1 \leq i < k$ 依次交换 $a_{b_i}$ 与 $a_{b_{i+1}}$ ,你可以认为每进行一次批量交换操作所用的时间为 1s。

kblack 准备了 $n$ 道题,但由于沉迷吃鸡,kblack 在出题时搞错了题目难度的顺序,第 $i$ 道题的难度是 $h_i$,保证 $h_i$ 是 $1$~$n$ 的一个排列。他需要利用 Polygon 系统交换题目,使得第 $i$ 道题的难度为 $i$。

下一个毒圈竟然刷在了对角线!kblack 必须尽快开始跑毒,所以他希望操作的耗时尽可能短。同时,由于 kblack 很懒,你还要告诉他每次操作的参数 $k$ 与 $b_1, b_2, \ldots, b_k$。

kblack 只想要快速解决问题!所以你只需要输出耗时最短的任意一个可行的方案即可。

输入格式

第一行输入一个整数 $n$ 表示题目的数量,且 $1 \leq n \leq 300~000$。

第二行输入 $n$ 个整数,第 $i$ 个整数表示 $h_i$。

输出格式

第一行输出一个整数 $m$ 表示进行的操作总次数。

第 $1+i$ 行输出 $1+k_i$ 个整数,第一个整数 $k_i$ 表示第 $i$ 次操作的参数 $k$,之后 $k_i$ 个整数表示第 $i$ 次的参数 $b_1, b_2, \ldots, b_{k_i}$。

样例

Input
2
2 1
Output
1
2 2 1
Input
3
1 3 2
Output
1
2 2 3
Input
3
2 3 1
Output
1
3 2 1 3
Input
4
3 4 1 2
Output
2
2 2 1
4 1 3 2 4

3 人解决,9 人已尝试。

3 份提交通过,共有 31 份提交。

9.1 EMB 奖励。

创建: 7 年,2 月前.

修改: 7 年,2 月前.

最后提交: 1 年,5 月前.

来源: 2017.9.27 ACM 选拔赛

题目标签