1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import sys
import typing
import collections


def _debug(*args):
    print(*args, file=sys.stderr)


def solve(items: typing.List[int]) -> typing.List[typing.List[int]]:
    index_array = [*enumerate(items)]
    index_array.sort(key=lambda x: x[1])
    visited_indices = {i: False for i in range(len(items))}
    cycles = []
    for i in range(len(items)):
        if visited_indices[i] or index_array[i][0] == i:
            continue
        j = i
        cycle = collections.deque()
        while not visited_indices[j]:
            visited_indices[j] = True
            pj = j
            j = index_array[pj][0]
            cycle.appendleft((j, pj))
        cycles.append(cycle)
    if not cycles:
        return []  # Already sorted
    result = []
    for cycle in cycles:
        cycle.pop() # Remove ending return cycle; not needed and compicates logic below
    while True:
        lefts = collections.deque()
        rights = collections.deque()
        all_processed = True
        for cycle in cycles:
            if len(cycle) > 0:
                all_processed = False
                l, r = cycle.pop()
                lefts.append(l)
                rights.appendleft(r)
        if all_processed:
            break
        result.append(list(lefts + rights))
    return result


def main():
    readline = sys.stdin.readline
    write = sys.stdout.write
    n = int(readline().strip())
    items = [int(readline().strip()) for _ in range(n)]
    steps = solve(items)
    write(f'{len(steps)}')
    for step in steps:
        write(f'\n{len(step)}\n')
        for pi in step:
            write(f'{pi+1} ')


if __name__ == '__main__':
    main()