← 返回题目列表

Codeforces · 843/A

A. 按子序列排序

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

给定一个序列 a1, a2, ...,由不同的整数组成。要求将这个序列分割成最大数量的子序列,使得每个子序列中的整数按升序排序后,整个序列也按升序排序。

对子序列中的整数进行排序是这样的过程:子序列中包含的数字按升序排列,子序列中不包含的数字不改变其位置。

序列的每个元素必须恰好出现在一个子序列中。

输入

输入数据的第一行包含整数 n (1 ≤ n ≤ 105) — 序列的长度。

输入数据的第二行包含 n 个不同的整数 a1, a2, ..., an (- 109 ≤ ai ≤ 109) — 序列的元素。保证序列的所有元素都是不同的。

输出

第一行打印在满足要求的情况下原序列可以分割成的最大子序列数k。

在接下来的 k 行中,按以下格式打印子序列的描述:子序列 ci (0 < ci ≤ n) 中的元素数量,然后是 ci 整数 l1, l2, ..., lci (1 ≤ lj ≤ n) - 这些元素在原始序列中的索引。

索引可以按任何顺序打印。从 1 到 n 的每个索引必须在输出中恰好出现一次。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

6
3 2 1 6 5 4

输出 #1

4
2 1 3
1 2
2 4 6
1 5

输入 #2

6
83 -75 -49 11 37 62

输出 #2

1
6 1 2 3 4 5 6

注意

在第一个示例输出中:

对第一个子序列进行排序后,我们将得到序列 1 2 3 6 5 4。

对第二个子序列进行排序不会改变任何内容。

对第三个子序列进行排序后,我们将得到序列 1 2 3 4 5 6。

对最后一个子序列进行排序不会改变任何内容。