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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import sys


def to_cycle_notation(heights):
    cycles = []
    used = set()
    for i in range(len(heights)):
        if i in used:
            continue

        cycle_start = i
        cycle = [i]
        used.add(i)

        next = heights[cycle_start][1]
        while next != cycle_start:
            cycle.append(next)
            used.add(next)
            next = heights[next][1]

        cycles.append(cycle)

    return cycles


def get_swaps(heights):
    cycles = to_cycle_notation(heights)

    swaps = []
    for c in cycles:
        if len(c) < 2:
            continue

        if len(c) == 2:
            swaps.append((c[0], c[1]))
            continue

        for i in range((len(c) - 1) // 2):
            swaps.append((c[i], c[-i - 2]))

    if len(swaps) == 0:
        return None

    return swaps


if __name__ == "__main__":
    n = int(input())
    heights = []
    for i in range(n):
        h = int(input())
        heights.append(h)

    heights_sorted = [(h, i) for i, h in enumerate(heights)]
    heights_sorted.sort()

    for sorted_i, (h, i) in enumerate(heights_sorted):
        heights[i] = (h, sorted_i)

    rounds = []
    swaps = get_swaps(heights)
    while swaps is not None:
        rounds.append(swaps)
        for s in swaps:
            heights[s[0]], heights[s[1]] = heights[s[1]], heights[s[0]]
        swaps = get_swaps(heights)

    print(len(rounds))
    for swaps in rounds:
        print(len(2 * swaps))
        print(
            " ".join(
                [str(s[0] + 1) for s in swaps] + [str(s[1] + 1) for s in swaps[-1::-1]]
            )
        )

    # if any([h1[0] != h2[0] for h1, h2 in zip(heights, heights_sorted)]):
    #     print("WRONG!!! Heights not sorted", file=sys.stderr)

    # if len(rounds) > 2:
    #     print("ERROR!!! Too many rounds!", file=sys.stderr)