Connectivity of a Permutation Graph

A permutation of size $n$ is a sequence of length $n$ in which every integer from $1$ to $n$ appears exactly once. Denote such a permutation by $a_1, a_2, \dots, a_n$.

From a permutation $a$ we build a permutation graph: an undirected graph on vertices numbered $1, 2, \dots, n$, in which two vertices $i$ and $j$ ($1 \le i < j \le n$) are joined by an edge whenever $a_i > a_j$.

Find all connected components of this graph. Scanning the vertices from the smallest index to the largest, whenever you reach a vertex that has not been visited yet, gather it together with every vertex reachable from it into a single set (a connected component).

Because $n$ can be as large as $1\,000\,000$, the graph may contain up to $O(n^2)$ edges, so building every edge and running a naive depth-first search is too slow. Use the structure of the permutation to find the connected components efficiently.

The first line contains the length of the permutation $n$ ($1 \le n \le 1\,000\,000$).

The second line contains $n$ space-separated integers, the elements $a_1, a_2, \dots, a_n$ of the permutation.

On the first line, print the number of connected components $m$.

On each of the next $m$ lines, print one component: first its size $s_i$, then the $s_i$ vertex numbers belonging to it in ascending order, separated by spaces.

When printing several components, sort them in ascending order by the smallest vertex number contained in each component.

The picture below shows the permutation graph built from the permutation in the first example.