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 from collections import defaultdict def get_perm(): n = int(input()) numbers = [(int(input()), i) for i in range(n)] numbers = [i for _, i in sorted(numbers)] return numbers def find_cycles(perm): cycles = [] visited = set() for start in range(len(perm)): if start in visited: continue cycle = [start] pos = start while True: pos = perm[pos] if pos == start: break cycle.append(pos) visited |= set(cycle) cycles.append(cycle) return cycles def adjust_swaps(swaps_d, cycle): # print(cycle) n = len(cycle) if n < 2: return if n == 2: swaps_d[1].append(tuple(cycle)) return beg, en = 0, len(cycle) - 2 while beg < en: swaps_d[1].append((cycle[beg], cycle[en])) cycle[beg], cycle[en] = cycle[en], cycle[beg] beg += 1 en -= 1 for i in range(n // 2): swaps_d[2].append((cycle[i], cycle[n - i - 1])) # 1220 1333 1863 2014 1449 1556 # 1220 1333 def print_answer(swaps_d): print(len(swaps_d.keys())) for l in swaps_d.values(): left, right = [], [] for x, y in l: left.append(x) right.append(y) res = left + right[::-1] print(len(res)) print(" ".join([str(e + 1) for e in res])) perm = get_perm() cycles = find_cycles(perm) swaps_d = defaultdict(list) for cycle in cycles: adjust_swaps(swaps_d, cycle) print_answer(dict(swaps_d))