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
n =  int(input())

h = [int(input()) for _ in range(n)]

sh = list(sorted(h))
a = list(range(n))

d = {}
for i, j in zip(sh, a):
    d[i] = j

for i in range(n):
    h[i] = d[h[i]]


res = 0
sh = list(sorted(h))
answer = ''
while h != sh:
    swaps_left = []
    swaps_right = []

    nbh = {}
    for i in range(n):
        nbh[i] = h[i]

    visited = [False for _ in range(n)]

    for i in range(n):
        nxt = i
        d = {}
        cnt = 0
        while not visited[nxt]:
            visited[nxt] = True
            d[cnt] = nxt
    
            nxt = nbh[nxt]
            cnt += 1

        l = len(d)

        if l == 2:
            x = d[0]
            y = d[1]
            swaps_left += [x + 1]
            swaps_right += [y + 1]

            tmp = h[x]
            h[x] = h[y]
            h[y] = tmp


        for j in range(1, l//2 + l%2):
            x = d[j]
            y = d[l - j]

            if x != y:
                swaps_left += [x + 1]
                swaps_right += [y + 1]

            tmp = h[x]
            h[x] = h[y]
            h[y] = tmp

    res += 1

    swaps = swaps_left + swaps_right[::-1]
    answer += str(len(swaps)) + '\n'
    answer += ' '.join(map(str, swaps)) + '\n'

print(res)
print(answer, end='')