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
from sys import stdin, stdout

def to_cycles(perm):
    perm = perm.copy()
    res = []
    for i in range(len(perm)):
        if perm[i] == 0:
            continue # already visited
        cycle = [i+1]
        j = i
        while perm[j] != i+1:
            cycle.append(perm[j])
            next_j = perm[j] - 1
            perm[j] = 0
            j = next_j
        perm[j] = 0
        res.append(cycle)
    return res

def generate_cycle(cycle):
    k = len(cycle)
    return [cycle[1:(k+1)//2], cycle[k//2+1:], cycle[:k//2], cycle[(k+1)//2:]]


n = int(stdin.readline())

height = [0] * n
for i in range(n):
    height[i] = int(stdin.readline())

perm = sorted(range(1, n+1), key=lambda i: height[i-1])
cycles = to_cycles(perm)

if all([len(c) == 1 for c in cycles]):
    stdout.write("0\n")
elif all([len(c) <=2 for c in cycles]):
    stdout.write("1\n")
    pairs = [c for c in cycles if len(c) == 2]
    stdout.write(str(len(pairs)*2) + "\n")
    res = [c[0] for c in pairs] + [c[1] for c in reversed(pairs)]
    stdout.write(" ".join([str(x) for x in res])+"\n")
else:
    stdout.write("2\n")
    res_components = [[], [], [], []]
    for c in cycles:
        gen = generate_cycle(c)
        for i in range(4):
            res_components[i].append(gen[i])
    res = [[], []]
    res[0] = [i for x in res_components[0] for i in x] + [i for x in reversed(res_components[1]) for i in x]
    res[1] = [i for x in res_components[2] for i in x] + [i for x in reversed(res_components[3]) for i in x]
    stdout.write(str(len(res[0])) + "\n")
    stdout.write(" ".join([str(x) for x in res[0]])+"\n")
    stdout.write(str(len(res[1])) + "\n")
    stdout.write(" ".join([str(x) for x in res[1]])+"\n")