#P14105. [ZJCPC 2017] Heap Partition

[ZJCPC 2017] Heap Partition

题目描述

A sequence S={s1,s2,,sn}S=\{s_1,s_2,\dots,s_n\} is called heapable\textit{heapable} if there exists a binary tree TT with nn nodes such that every node is labelled with exactly one element from the sequence SS, and for every non-root node sis_i and its parent sjs_j, sjsis_j \le s_i and j<ij < i hold. Each element in sequence SS can be used to label a node in tree TT only once.

Chiaki has a sequence a1,a2,,ana_1,a_2,\dots,a_n, she would like to decompose it into a minimum number of heapable subsequences.

Note that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

输入格式

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:

The first line contain an integer nn (1n1051 \le n \le 10^5) -- the length of the sequence.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n).

It is guaranteed that the sum of all nn does not exceed 2×1062 \times 10^6.

输出格式

For each test case, output an integer mm denoting the minimum number of heapable subsequences in the first line. For the next mm lines, first output an integer CiC_i, indicating the length of the subsequence. Then output CiC_i integers Pi1,Pi2,,PiCiP_{i1}, P_{i2}, \dots, P_{iC{_i}} in increasing order on the same line, where PijP_{ij} means the index of the jj-th element of the ii-th subsequence in the original sequence.

4
4
1 2 3 4
4
2 4 3 1
4
1 1 1 1
5
3 2 1 4 1
1
4 1 2 3 4
2
3 1 2 3
1 4
1
4 1 2 3 4
3
2 1 4
1 2
2 3 5