3360. 多边形排序

单点时限: 1.5 sec

内存限制: 256 MB

章鱼哥在 EOJ 中加入了万众期待的 Polygon 系统,这个系统最大的特色就是可以快速对题目的顺序进行批量交换。Polygon 中只提供了一种交换操作,对于一个长度为 n 题目序列 a1,a2,,an,你可以任意选取 b1,b2,,bk (2kn,1bin)b1,b2,,bk 互不相等,但大小顺序任意,在进行交换操作时,系统对 1i<k 依次交换 abiabi+1 ,你可以认为每进行一次批量交换操作所用的时间为 1s。

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

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

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

输入格式

第一行输入一个整数 n 表示题目的数量,且 1n300 000

第二行输入 n 个整数,第 i 个整数表示 hi

输出格式

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

1+i 行输出 1+ki 个整数,第一个整数 ki 表示第 i 次操作的参数 k,之后 ki 个整数表示第 i 次的参数 b1,b2,,bki

样例

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 人解决,10 人已尝试。

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

9.1 EMB 奖励。

创建: 7 年,6 月前.

修改: 7 年,6 月前.

最后提交: 2 周,3 天前.

来源: 2017.9.27 ACM 选拔赛

题目标签