148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - F

Heap Partition

Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge

A sequence `S` = {`s`_{1}, `s`_{2}, ..., `s`_{n}} is called *heapable* if there exists a binary tree `T` with `n` nodes such that every node is labelled with exactly one element from the sequence `S`, and for every non-root node `s`_{i} and its parent `s`_{j}, `s`_{j} ≤ `s`_{i} and `j` < `i` hold. Each element in sequence `S` can be used to label a node in tree `T` only once.

Chiaki has a sequence `a`_{1}, `a`_{2}, ..., `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.

#### Input

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

The first line contain an integer `n` (1 ≤ `n` ≤ 10^{5}) — the length of the sequence.

The second line contains `n` integers `a`_{1}, `a`_{2}, ..., `a`_{n} (1 ≤ `a`_{i} ≤ `n`).

It is guaranteed that the sum of all `n` does not exceed 2 × 10^{6}.

#### Output

For each test case, output an integer `m` denoting the minimum number of heapable subsequences in the first line. For the next `m` lines, first output an integer `C`_{i}, indicating the length of the subsequence. Then output `C`_{i} integers `P`_{i1}, `P`_{i2}, ..., `P`_{iCi} in increasing order on the same line, where `P`_{ij} means the index of the `j`-th element of the `i`-th subsequence in the original sequence.

#### Sample Input

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

#### Sample Output

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

#### Hint

Submit
Status