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
82
83
84
85
86
87
88
89
import random
import copy

def swap(heights, changes):
    for i in range(len(changes)//2):
        heights[changes[i] - 1], heights[changes[-i-1] - 1] = heights[changes[-i-1] - 1], heights[changes[i] - 1]
    # print(f"CHANGES: {changes}")
    # print(f"HEIGHTS: {heights}")


def solve(heights, output=False):
    sorted_heights = sorted(heights)
    visited = [False for _ in range(len(heights))]

    cycles = []
    max_size_cycle = 0
    for i in range(len(heights)):
        if visited[i]:
            continue
        visited[i] = True
        if heights[i] == sorted_heights[i]:
            continue
        cycle = [i+1]
        next_idx = sorted_heights.index(heights[i])
        while next_idx != i:
            visited[next_idx] = True
            cycle.append(next_idx+1)
            next_idx = sorted_heights.index(heights[next_idx])
        
        cycles.append(cycle)
        max_size_cycle = max(len(cycle), max_size_cycle)

    round = []
    for i, cycle in enumerate(cycles):
        if not cycle:
            continue
        if len(cycle) == 2:
            round = [cycle[0]] + round + [cycle[1]]
            cycles[i] = []
        else:
            for j in range(1, (len(cycle) + 1)//2):
                round = [cycle[j]] + round + [cycle[-j]]
    return round


def main():
    n = int(input())
    
    heights = []

    for i in range(n):
        heights.append(int(input()))

    # for _ in range(10_000):
    #     heights = random.sample(range(1000), random.randint(5, 300))
        # print(heights)
        # if not solve(copy.copy(heights), output=True):
        #     print(heights)
    # sorted_heights = sorted(heights)
    round1 = solve(heights, output=False)
    swap(heights, round1)
    round2 = solve(heights, output=False)
    # swap(heights, round2)

    if round2:
        print("2")
    elif round1:
        print("1")
    else:
        print("0")
        return

    print(len(round1))
    print(" ".join([str(x) for x in round1]))
    if round2:
        print(len(round2))
        print(" ".join([str(x) for x in round2]))

        # if sorted_heights != heights:
        #     print(heights)
   

    # print(heights)

    


if __name__ == '__main__':
    main()