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
class Student():
    def __init__(self, height) -> None:
        self.height = height
        self.pos = None
        self.pos_e = None
    
    def __str__(self):
        return f'pos: {self.pos}, pos_e: {self.pos_e}'

if __name__ == '__main__':
    n = int(input())
    output = []
    students = []
    for i in range(n):
        height = int(input())
        students.append(Student(height))
        students[-1].pos = i
    students.sort(key=lambda x: x.height)
    for i in range(n):
        students[i].pos_e = i
    students.sort(key=lambda x: x.pos)

    status = ['ERROR' for _ in range(n)]

    ok = 0
    for i in range(n):
        if i == students[i].pos_e:
            ok += 1
            status[i] = 'OK'

    while ok < n:
        for i in range(n):
            if status[i] == 'BUSY':
                status[i] = 'ERROR'
        new_line = []
        for i in range(n):
            if status[i] == 'ERROR' and status[students[i].pos_e] == 'ERROR':
                x, y = i, students[i].pos_e
                new_line = [x] + new_line + [y]
                status[x] = 'BUSY'
                ok += 1
                status[y] = 'OK'
                if students[y].pos_e == x:
                    ok += 1
                    status[x] = 'OK'
                students[x], students[y] = students[y], students[x]

        output.append(new_line)     

    if len(output) > 2:
        if len(output[-1]) == 2 and len(output[-2]) == 2:
            A = set(output[-1])
            B = set(output[-2])
            if A.intersection(B):
                X = list(A.intersection(B))[0]
                A_dop = list(A.difference(B))[0]
                B_dop = list(B.difference(A))[0]
                is_A = A_dop in output[-3]
                is_B = B_dop in output[-3]
                Y = None
                for i in range(len(output[-3])):
                    Y = output[-3][len(output[-3]) - i - 1]
                    if output[-3][i] == X:
                        if is_A:
                            output[-3][i] = B_dop
                        elif is_B:
                            output[-3][i] = A_dop
                        break
               
                output[-2] = [X, A_dop, B_dop, Y]
                output = output[:-1]

    print(len(output))
    for line in output:
        print(len(line))
        for el in line:
            print(el + 1, end=' ')                 
        print()