순열 그래프의 연결성 판별

크기가 $n$인 순열은 $1$부터 $n$까지의 정수가 정확히 한 번씩 등장하는 길이 $n$의 수열이다. 이 순열을 $a_1, a_2, \dots, a_n$ 이라고 하자.

순열 $a$로부터 다음과 같이 순열 그래프를 만든다. 순열 그래프는 $1, 2, \dots, n$번 정점으로 이루어진 무방향 그래프이며, 두 정점 $i$, $j$ ($1 \le i < j \le n$)는 $a_i > a_j$ 일 때 간선으로 연결된다.

이 순열 그래프의 연결 요소(connected component)를 모두 구하려고 한다. 정점을 번호가 작은 쪽부터 큰 쪽으로 살펴보다가 아직 방문하지 않은 정점을 만나면, 그 정점에서 도달할 수 있는 모든 정점을 함께 모아 하나의 집합(연결 요소)으로 묶는다.

$n$이 최대 $1\,000\,000$까지 커질 수 있어 간선 수가 $O(n^2)$에 이를 수 있으므로, 모든 간선을 만들어 단순한 깊이 우선 탐색을 수행하면 시간 안에 끝나지 않는다. 순열의 구조를 이용하여 연결 요소를 효율적으로 구하라.

첫째 줄에 순열의 길이 $n$ ($1 \le n \le 1\,000\,000$)이 주어진다.

둘째 줄에 공백으로 구분된 $n$개의 정수가 주어지며, 이는 순열의 원소 $a_1, a_2, \dots, a_n$을 나타낸다.

첫째 줄에 연결 요소의 개수 $m$을 출력한다.

이어지는 $m$개의 줄에 각 연결 요소를 출력한다. 각 줄에는 먼저 그 요소에 속한 정점의 개수 $s_i$를 출력하고, 이어서 그 요소에 속한 $s_i$개의 정점 번호를 오름차순으로 공백으로 구분하여 출력한다.

여러 연결 요소를 출력할 때에는, 각 요소에 속한 가장 작은 정점 번호를 기준으로 오름차순으로 정렬하여 출력한다.

아래 그림은 첫 번째 예제의 순열로 만든 순열 그래프를 나타낸다.