{"raw_statement":[{"iden":"statement","content":"Yesterday was a fair in a supermarket's grocery section. There were _n_ jars with spices on the fair. Before the event the jars were numbered from 1 to _n_ from the left to the right. After the event the jars were moved and the grocer had to sort them by the increasing of the numbers.\n\nThe grocer has a special machine at his disposal. The machine can take any 5 or less jars and rearrange them in the way the grocer wants. Note that the jars **do not have to** stand consecutively. For example, from the permutation 2, 6, 5, 4, 3, 1 one can get permutation 1, 2, 3, 4, 5, 6, if pick the jars on the positions 1, 2, 3, 5 and 6.\n\nWhich minimum number of such operations is needed to arrange all the jars in the order of their numbers' increasing?"},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 105). The second line contains _n_ space-separated integers _a__i_ (1 ≤ _a__i_ ≤ _n_) — the _i_\\-th number represents the number of a jar that occupies the _i_\\-th position. It is guaranteed that all the numbers are distinct."},{"iden":"output","content":"Print on the first line the least number of operations needed to rearrange all the jars in the order of the numbers' increasing. Then print the description of all actions in the following format.\n\nOn the first line of the description of one action indicate the number of jars that need to be taken (_k_), on the second line indicate from which positions the jars need to be taken (_b_1, _b_2, ..., _b__k_), on the third line indicate the jar's new order (_c_1, _c_2, ..., _c__k_). After the operation is fulfilled the jar from position _b__i_ will occupy the position _c__i_. The set (_c_1, _c_2, ..., _c__k_) should be the rearrangement of the set (_b_1, _b_2, ..., _b__k_).\n\nIf there are multiple solutions, output any."},{"iden":"examples","content":"Input\n\n6\n3 5 6 1 2 4\n\nOutput\n\n2\n4\n1 3 6 4 \n3 6 4 1 \n2\n2 5 \n5 2 \n\nInput\n\n14\n9 13 11 3 10 7 12 14 1 5 4 6 8 2\n\nOutput\n\n3\n4\n2 13 8 14 \n13 8 14 2 \n5\n6 7 12 5 10 \n7 12 6 10 5 \n5\n3 11 4 1 9 \n11 4 3 9 1"},{"iden":"note","content":"Let's consider the first sample. The jars can be sorted within two actions.\n\nDuring the first action we take the jars from positions 1, 3, 6 and 4 and put them so that the jar that used to occupy the position 1 will occupy the position 3 after the operation is completed. The jar from position 3 will end up in position 6, the jar from position 6 will end up in position 4 and the jar from position 4 will end up in position 1.\n\nAfter the first action the order will look like that: 1, 5, 3, 4, 2, 6.\n\nDuring the second operation the jars in positions 2 and 5 will change places."}],"translated_statement":[{"iden":"statement","content":"昨天超市的香料区举办了一场集市。集市上有 #cf_span[n] 个装有香料的罐子，活动前这些罐子从左到右编号为 #cf_span[1] 到 #cf_span[n]。活动结束后，罐子被移动了，店员需要按照编号递增的顺序重新排列它们。\n\n店员有一台专用机器，可以取出任意 #cf_span[5] 个或更少的罐子，并按店员希望的顺序重新摆放。注意，罐子 *不必* 连续放置。例如，从排列 #cf_span[2], #cf_span[6], #cf_span[5], #cf_span[4], #cf_span[3], #cf_span[1] 中，如果选取位置为 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[5] 和 #cf_span[6] 的罐子，就可以得到排列 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[5], #cf_span[6]。\n\n问最少需要多少次这样的操作，才能将所有罐子按编号递增的顺序排列？\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ n])，其中第 #cf_span[i] 个数表示占据第 #cf_span[i] 个位置的罐子编号。保证所有数字互不相同。\n\n请在第一行输出将所有罐子按编号递增顺序排列所需的最少操作次数。然后按以下格式输出所有操作的描述。\n\n对于每个操作，第一行输出需要取出的罐子数量 #cf_span[k]，第二行输出从哪些位置取出罐子（#cf_span[b1, b2, ..., bk]），第三行输出罐子的新位置顺序（#cf_span[c1, c2, ..., ck]）。操作完成后，原来位于位置 #cf_span[bi] 的罐子将移动到位置 #cf_span[ci]。集合 (#cf_span[c1, c2, ..., ck]) 应为集合 (#cf_span[b1, b2, ..., bk]) 的重排。\n\n如果有多种解法，输出任意一种即可。\n\n考虑第一个样例：罐子可以在两次操作内完成排序。\n\n第一次操作中，我们取出位置为 #cf_span[1], #cf_span[3], #cf_span[6], #cf_span[4] 的罐子，并重新摆放：原来在位置 #cf_span[1] 的罐子最终位于位置 #cf_span[3]，原来在位置 #cf_span[3] 的罐子最终位于位置 #cf_span[6]，原来在位置 #cf_span[6] 的罐子最终位于位置 #cf_span[4]，原来在位置 #cf_span[4] 的罐子最终位于位置 #cf_span[1]。\n\n第一次操作后，顺序变为：#cf_span[1], #cf_span[5], #cf_span[3], #cf_span[4], #cf_span[2], #cf_span[6]。\n\n第二次操作中，位置 #cf_span[2] 和 #cf_span[5] 的罐子交换位置。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ n])，其中第 #cf_span[i] 个数表示占据第 #cf_span[i] 个位置的罐子编号。保证所有数字互不相同。"},{"iden":"output","content":"请在第一行输出将所有罐子按编号递增顺序排列所需的最少操作次数。然后按以下格式输出所有操作的描述。\n对于每个操作，第一行输出需要取出的罐子数量 #cf_span[k]，第二行输出从哪些位置取出罐子（#cf_span[b1, b2, ..., bk]），第三行输出罐子的新位置顺序（#cf_span[c1, c2, ..., ck]）。操作完成后，原来位于位置 #cf_span[bi] 的罐子将移动到位置 #cf_span[ci]。集合 (#cf_span[c1, c2, ..., ck]) 应为集合 (#cf_span[b1, b2, ..., bk]) 的重排。\n如果有多种解法，输出任意一种即可。"},{"iden":"examples","content":"输入\n6\n3 5 6 1 2 4\n输出\n2\n4\n1 3 6 4\n3 6 4 1\n2\n2 5\n5 2\n\n输入\n14\n9 13 11 3 10 7 12 14 1 5 4 6 8 2\n输出\n3\n4\n2 13 8 14\n13 8 14 2\n5\n6 7 12 5 10\n7 12 6 10 5\n3\n11 4 1\n9 11 4\n9 1 "},{"iden":"note","content":"考虑第一个样例：罐子可以在两次操作内完成排序。\n\n第一次操作中，我们取出位置为 #cf_span[1], #cf_span[3], #cf_span[6], #cf_span[4] 的罐子，并重新摆放：原来在位置 #cf_span[1] 的罐子最终位于位置 #cf_span[3]，原来在位置 #cf_span[3] 的罐子最终位于位置 #cf_span[6]，原来在位置 #cf_span[6] 的罐子最终位于位置 #cf_span[4]，原来在位置 #cf_span[4] 的罐子最终位于位置 #cf_span[1]。\n\n第一次操作后，顺序变为：#cf_span[1], #cf_span[5], #cf_span[3], #cf_span[4], #cf_span[2], #cf_span[6]。\n\n第二次操作中，位置 #cf_span[2] 和 #cf_span[5] 的罐子交换位置。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ \\pi \\in S_n $ be a permutation representing the current arrangement of jars: $ \\pi(i) $ is the label of the jar at position $ i $.\n- The goal is to transform $ \\pi $ into the identity permutation $ \\text{id}(i) = i $.\n- An operation allows selecting any subset of up to 5 positions and arbitrarily permuting the jars at those positions.\n\n**Given:**\n\n- $ n \\in \\mathbb{N}, \\; 1 \\leq n \\leq 10^5 $\n- A permutation $ \\pi = [\\pi(1), \\pi(2), \\dots, \\pi(n)] $, where all $ \\pi(i) \\in \\{1, 2, \\dots, n\\} $ are distinct.\n\n**Objective:**\n\nFind the minimum number of operations (each operating on at most 5 positions) to sort $ \\pi $ into ascending order $ [1, 2, \\dots, n] $, and output a sequence of such operations.\n\n---\n\n**Mathematical Formulation:**\n\nLet $ \\sigma = \\pi^{-1} $ be the permutation such that $ \\sigma(j) $ is the current position of the jar labeled $ j $.  \nThen, sorting $ \\pi $ to identity is equivalent to sorting $ \\sigma $ to $ \\text{id} $, i.e., moving each element $ j $ from position $ \\sigma(j) $ to position $ j $.\n\nEquivalently, define the *target permutation* $ \\tau $ such that $ \\tau(i) = \\pi(i) $, and we wish to reach $ \\tau' = \\text{id} $.  \nThe permutation mapping current to target is $ \\rho = \\text{id} \\circ \\pi^{-1} = \\pi^{-1} $, so $ \\rho(i) = j $ means the jar at position $ i $ should go to position $ j $.\n\nThus, we are to decompose $ \\rho = \\pi^{-1} $ into a product of permutations, each acting on at most 5 elements (i.e., each operation is a permutation on a subset of size $ \\leq 5 $), and minimize the number of such factors.\n\n**Key Insight:**\n\n- Any permutation can be decomposed into disjoint cycles.\n- Each cycle of length $ \\ell $ can be sorted using $ \\left\\lceil \\frac{\\ell}{4} \\right\\rceil $ operations, because:\n  - A cycle of length $ \\ell $ requires $ \\ell - 1 $ transpositions to resolve.\n  - Each operation can resolve up to 4 elements (since 5 elements can be rearranged to fix 4 misplaced elements in one move — one element is used as a pivot or is already in place).\n  - More precisely: in one operation on $ k \\leq 5 $ positions, we can fix up to $ k - 1 $ elements (if arranged optimally).\n  - Thus, a cycle of length $ \\ell $ can be resolved in $ \\left\\lceil \\frac{\\ell - 1}{4} \\right\\rceil $ operations.\n- However, since operations can act on *non-consecutive* positions and we are allowed to permute any 5 or fewer elements arbitrarily, we can handle multiple disjoint cycles simultaneously in one operation, *as long as the total number of positions involved is ≤ 5*.\n\nBut note: **operations are applied sequentially**, and each operation can act on any 5 or fewer positions — even if they belong to different cycles.\n\nThus, the minimal number of operations is:\n\n$$\n\\boxed{ \\left\\lceil \\frac{c}{1} \\right\\rceil }\n$$\n\nWait — better approach:\n\nActually, since each operation can handle up to 5 elements, and each misplaced element must be moved at least once, we can think greedily:\n\n- Let $ m $ be the number of elements that are **not** in their correct position (i.e., $ |\\{ i : \\pi(i) \\ne i \\}| $).\n- Each operation can fix up to 5 elements (if we move 5 misplaced elements into their correct positions in one go).\n- So a lower bound is $ \\left\\lceil \\frac{m}{5} \\right\\rceil $.\n\nBut is this tight? **Yes**, because:\n\n- We can always find a set of up to 5 misplaced elements and permute them so that **each** of them goes to its correct position, **provided** the mapping among them forms a derangement that is solvable within the 5-permutation.\n- Since any derangement of up to 5 elements can be sorted in one operation (by applying the inverse permutation), we can always fix up to 5 misplaced elements per operation.\n\nThus, the **minimum number of operations** is:\n\n$$\n\\boxed{ \\left\\lceil \\frac{m}{5} \\right\\rceil }\n$$\n\nwhere $ m = |\\{ i \\in [n] : \\pi(i) \\ne i \\}| $.\n\n---\n\n**Algorithm to Construct Operations:**\n\n1. Compute $ m = $ number of indices $ i $ such that $ \\pi(i) \\ne i $.\n2. Let $ S = \\{ i \\in [n] : \\pi(i) \\ne i \\} $ — the set of misplaced positions.\n3. While $ S \\ne \\emptyset $:\n   - Pick up to 5 elements from $ S $, say $ \\{i_1, i_2, \\dots, i_k\\} $, $ k \\leq 5 $.\n   - Let $ a_j = \\pi(i_j) $ — the jar currently at position $ i_j $.\n   - We want to assign each jar $ a_j $ to position $ a_j $ (since jar $ x $ should be at position $ x $).\n   - Define a permutation $ \\sigma $ on the set $ \\{i_1, \\dots, i_k\\} $ such that:\n     $$\n     \\sigma(i_j) = a_j\n     $$\n     But we need to move the jar from $ i_j $ to position $ a_j $, so we want a mapping from *current positions* to *target positions*:\n     - We are going to reassign the jars at positions $ i_1, \\dots, i_k $ to positions $ a_1, \\dots, a_k $, **but** we must ensure that the set $ \\{a_1, \\dots, a_k\\} $ is exactly $ \\{i_1, \\dots, i_k\\} $ — which may not hold.\n\nWait — correction:\n\nWe have:  \nAt position $ i $, jar $ \\pi(i) $ is present.  \nWe want jar $ j $ to be at position $ j $.  \nSo, for each $ i \\in S $, the jar $ \\pi(i) $ needs to go to position $ \\pi(i) $.\n\nThus, we have a mapping:  \nCurrent position $ i \\mapsto $ target position $ \\pi(i) $.\n\nThis defines a permutation $ f: S \\to \\mathbb{N} $, $ f(i) = \\pi(i) $.\n\nWe want to find a permutation $ \\sigma $ on a subset $ T \\subseteq S $, $ |T| \\leq 5 $, such that applying $ \\sigma $ to the positions in $ T $ moves each jar from position $ i $ to position $ f(i) $.\n\nBut note: $ f(i) $ may not be in $ T $ — so we cannot fix it in isolation.\n\n**Better approach: use cycle decomposition.**\n\nLet $ \\rho = \\pi^{-1} $. Then $ \\rho(j) = i $ means jar $ j $ is currently at position $ i $, and should go to position $ j $.  \nSo the permutation $ \\rho $ describes where each jar needs to go.\n\nDecompose $ \\rho $ into disjoint cycles.\n\nEach cycle $ (a_1 \\; a_2 \\; \\dots \\; a_\\ell) $ means:\n- Jar $ a_1 $ is at position $ a_2 $,\n- Jar $ a_2 $ is at position $ a_3 $,\n- ...\n- Jar $ a_\\ell $ is at position $ a_1 $.\n\nTo fix this cycle, we can apply a single operation on the $ \\ell $ positions $ \\{a_2, a_3, \\dots, a_\\ell, a_1\\} $ and permute the jars so that jar $ a_i $ goes to position $ a_i $.\n\nBut we can only act on up to 5 positions per operation.\n\nSo:\n\n- For each cycle of length $ \\ell $, we can break it into $ \\left\\lceil \\frac{\\ell}{4} \\right\\rceil $ operations, because:\n  - In one operation, we can fix 4 elements of the cycle (i.e., move 4 jars to their correct positions), leaving one to be handled later.\n  - But actually, we can fix a whole cycle of length $ \\ell \\leq 5 $ in one operation.\n\nThus:\n\n> **Minimum number of operations = number of cycles of length > 1**, **but** we can combine multiple small cycles into one operation if total number of elements involved ≤ 5.\n\nSo the optimal strategy is:\n\n- Decompose $ \\rho = \\pi^{-1} $ into disjoint cycles.\n- Ignore fixed points (cycles of length 1).\n- Group the non-trivial cycles (length ≥ 2) into groups such that the total number of elements in each group is ≤ 5.\n- Each group can be fixed in one operation: since we can permute any subset of positions arbitrarily, we can rearrange all jars in the selected positions to their correct destinations in one go.\n\nThus, the minimal number of operations is the **minimum number of groups** we can partition the non-fixed elements into, such that each group has size ≤ 5.\n\nThis is equivalent to:\n\n$$\n\\boxed{ \\left\\lceil \\frac{m}{5} \\right\\rceil }\n$$\n\nwhere $ m = $ number of non-fixed elements.\n\nAnd since we can always group the elements arbitrarily (because any permutation of up to 5 elements can be achieved in one operation), this bound is achievable.\n\n---\n\n**Final Answer Format:**\n\n- First line: $ \\left\\lceil \\frac{m}{5} \\right\\rceil $\n- Then, for each operation:\n  - First line: $ k $ (number of jars, $ 2 \\leq k \\leq 5 $)\n  - Second line: $ k $ positions (current positions of the jars to move)\n  - Third line: $ k $ target positions (where each jar should go — i.e., the jar currently at position $ b_i $ should go to position $ c_i $)\n\nTo construct the operations:\n\n1. Let $ S = \\{ i : \\pi(i) \\ne i \\} $\n2. While $ S \\ne \\emptyset $:\n   - Take the first $ \\min(5, |S|) $ elements from $ S $, call this set $ T = \\{i_1, \\dots, i_k\\} $\n   - For each $ i_j \\in T $, the jar $ \\pi(i_j) $ should go to position $ \\pi(i_j) $\n   - So we want to assign the jar from position $ i_j $ to position $ \\pi(i_j) $\n   - Let $ c_j = \\pi(i_j) $\n   - Now, we must ensure that the mapping $ i_j \\mapsto c_j $ is a permutation of $ T $ — but it might not be, because $ c_j $ may not be in $ T $\n\nWait — here is the **critical point**:\n\nIf we pick a set $ T \\subseteq S $, and we want to move jars from positions in $ T $ to positions $ \\{\\pi(i) : i \\in T\\} $, then for the operation to be self-contained, we need $ \\{\\pi(i) : i \\in T\\} = T $. Otherwise, we are moving jars into/out of positions outside $ T $, which may mess up other elements.\n\nBut the problem allows us to move jars to **any** positions — even those not in the selected set. However, the operation is defined as:\n\n> \"The jar from position $ b_i $ will occupy the position $ c_i $\"\n\nAnd $ c_i $ can be any position (not necessarily in the selected set). But the problem says: \"take any 5 or less jars\" — meaning we select up to 5 jars (i.e., their current positions), and we can place them into **any** positions (even outside the selected ones).\n\nBut if we move a jar to a position not in our selected set, then we are overwriting a jar that we didn’t pick — which is not allowed, because we only took 5 jars.\n\nWait — re-read the problem:\n\n> \"The machine can take any 5 or less jars and rearrange them in the way the grocer wants. Note that the jars do not have to stand consecutively.\"\n\nAnd:\n\n> \"the jar from position $ b_i $ will occupy the position $ c_i $\"\n\nThis implies: we **remove** the jars at positions $ b_1, \\dots, b_k $, and then **place** them at positions $ c_1, \\dots, c_k $. So the positions $ c_i $ must be distinct and not conflict with other jars not selected.\n\nBut if we move a jar to a position not in $ \\{b_1, \\dots, b_k\\} $, then we are overwriting a jar that was not taken — which is not allowed.\n\nTherefore, **the set $ \\{c_1, \\dots, c_k\\} $ must be exactly $ \\{b_1, \\dots, b_k\\} $** — i.e., we are permuting the jars among the selected positions.\n\nSo the operation is a **permutation of the jars within the selected positions**.\n\nThus, we can only rearrange the jars among the $ k $ selected positions — we cannot move a jar from position $ i $ to position $ j $ if $ j \\notin \\{b_1, \\dots, b_k\\} $.\n\nThis changes everything.\n\nTherefore, **each operation can only permute jars among a set of up to 5 positions** — and cannot move jars into or out of those positions.\n\nSo the problem reduces to: we have a permutation $ \\pi $, and we can apply any permutation on any subset of up to 5 positions. We want to sort $ \\pi $ to identity.\n\nThis is equivalent to: decompose the permutation $ \\rho = \\pi^{-1} $ into a product of permutations, each supported on at most 5 elements.\n\nThe minimal number of such permutations needed is equal to the number of cycles in the cycle decomposition of $ \\rho $, **but** we can combine multiple small cycles into one operation if their total size ≤ 5.\n\nSo:\n\n- Let $ C_1, C_2, \\dots, C_t $ be the non-trivial cycles (length ≥ 2) of $ \\rho $.\n- Each cycle of length $ \\ell $ requires $ \\lceil \\ell / 4 \\rceil $ operations? No — we can fix a cycle of length $ \\ell \\leq 5 $ in one operation.\n\nBut we can combine multiple cycles into one operation **only if** the union of their elements has size ≤ 5.\n\nSo the problem reduces to: **bin packing** — pack the cycles into bins of size 5, where each cycle has size $ \\ell_i \\geq 2 $, and minimize the number of bins.\n\nThis is NP-hard in general, but since cycle lengths are at least 2 and at most $ n $, and $ n \\leq 10^5 $, but in practice, cycles are small, and we can use a greedy algorithm: sort cycles by size descending, and pack greedily.\n\nBut note: we are allowed to break a cycle into multiple operations. For example, a cycle of length 6 can be split into two operations: fix 4 elements in one, 2 in another.\n\nSo we don’t need to keep cycles intact.\n\nIn fact, **any set of up to 5 misplaced elements can be fixed in one operation**, as long as we permute them among themselves to their correct positions.\n\nBut the correct position of a jar may lie outside the selected set — so we cannot fix it unless we select its target position too.\n\nSo the only way to fix a jar is to include both its current position and its target position in the same operation.\n\nThus, we must select a set of positions such that the mapping $ i \\mapsto \\pi(i) $ forms a permutation on that set — i.e., the set is closed under the mapping $ i \\mapsto \\pi(i) $.\n\nIn other words, we must select a union of entire cycles — or parts of cycles? But if we take a subset of a cycle, the mapping may not be closed.\n\nActually, we can take any subset of positions and permute them arbitrarily — we are not restricted to preserving the cycle structure. We can move any jar from any selected position to any selected target position, regardless of where it \"should\" go according to the cycle.\n\nWait — no: the goal is to get jar $ j $ to position $ j $. So if we move jar $ \\pi(i) $ from position $ i $ to position $ \\pi(i) $, then it is fixed.\n\nBut to do that, we must select position $ i $ (where the jar is) and position $ \\pi(i) $ (where it should go) in the same operation — and then swap or permute them.\n\nBut if $ \\pi(i) $ is not in our selected set, we can't move the jar there.\n\nTherefore, **to fix a jar at position $ i $, we must include both $ i $ and $ \\pi(i) $ in the same operation**.\n\nThis means that we must select entire cycles or unions of cycles such that the mapping $ i \\mapsto \\pi(i) $ maps the selected set to itself.\n\nIn other words, the selected set must be a union of entire cycles.\n\nTherefore, we cannot break a cycle — we must fix each cycle in one or more operations, but we can combine multiple cycles into one operation if the total number of elements in the union of those cycles is ≤ 5.\n\nSo the problem reduces to: **Partition the set of non-trivial cycles into groups, such that the total number of elements in each group is ≤ 5, and minimize the number of groups.**\n\nThis is the **bin packing problem** with item sizes = cycle lengths, bin capacity = 5.\n\nSince cycle lengths are at least 2, and ≤ n, and n ≤ 10^5, but the number of cycles is at most n/2, we can use a greedy first-fit decreasing algorithm.\n\nBut note: the problem says \"if there are multiple solutions, output any\".\n\nSo we can use:\n\n- Collect all non-trivial cycles (length ≥ 2), store their sizes.\n- Sort them in descending order.\n- Use first-fit decreasing: for each cycle, place it in the first bin that has enough room.\n\nEach bin corresponds to one operation.\n\nFor each bin (group of cycles), the operation will permute all the positions in the union of those cycles to their correct destinations.\n\nHow to output the operation?\n\n- Let the selected positions be the union of all positions in the cycles assigned to this bin.\n- For each position $ i $ in this set, the jar at $ i $ is $ \\pi(i) $, and it should go to position $ \\pi(i) $.\n- So we create a mapping: from current position $ i $ to target position $ \\pi(i) $.\n- Since the set is closed under $ i \\mapsto \\pi(i) $, the target positions are exactly the same set.\n- So we output:\n  - k = size of the set\n  - list of current positions (any order)\n  - list of target positions: for each current position $ i $ in the same order, output $ \\pi(i) $\n\nThis will move each jar to its correct position.\n\n**Algorithm Summary:**\n\n1. Read $ n $, permutation $ \\pi[1..n] $\n2. Compute $ \\rho = \\pi^{-1} $: for $ j = 1 $ to $ n $, $ \\rho[\\pi[j]] = j $\n3. Find cycles of $ \\rho $ (i.e., the mapping from jar label to current position). Actually, we need the cycle decomposition of the permutation $ \\sigma $ defined by $ \\sigma(i) = \\rho(i) = $ position of jar $ i $, but we want the mapping from current position to target position.\n\nActually, define the permutation $ f $ on positions: $ f(i) = \\pi(i) $ — the label of the jar at position $ i $.  \nWe want to get to $ \\text{id}(i) = i $, so the permutation to sort is $ f $, and we want to apply transpositions to turn $ f $ into identity.\n\nThe permutation $ f $ can be decomposed into cycles.\n\nFor example, if $ \\pi = [2, 6, 5, 4, 3, 1] $, then:\n\n- Position 1 has jar 2 → should go to position 2\n- Position 2 has jar 6 → should go to position 6\n- Position 3 has jar 5 → should go to position 5\n- Position 4 has jar 4 → fixed\n- Position 5 has jar 3 → should go to position 3\n- Position 6 has jar 1 → should go to position 1\n\nSo the cycle structure of $ \\pi $ is: (1 2 6)(3 5) — since:\n- 1 → 2 → 6 → 1\n- 3 → 5 → 3\n\nSo we have two cycles: one of length 3, one of length 2.\n\nWe can put both in one operation since 3+2=5 ≤ 5.\n\nOperation: take positions {1,2,6,3,5}\n\nWe want:\n- jar at 1 (jar 2) → go to 2\n- jar at 2 (jar 6) → go to 6\n- jar at 6 (jar 1) → go to 1\n- jar at 3 (jar 5) → go to 5\n- jar at 5 (jar 3) → go to 3\n\nSo we need a permutation $ \\sigma $ such that:\n- $ \\sigma(1) = 2 $\n- $ \\sigma(2) = 6 $\n- $ \\sigma(6) = 1 $\n- $ \\sigma(3) = 5 $\n- $ \\sigma(5) = 3 $\n\nSo output:\n- k = 5\n- positions: 1 2 6 3 5\n- targets: 2 6 1 5 3\n\nAfter this, all jars are sorted.\n\nSo the algorithm is:\n\n1. Find all cycles of the permutation $ \\pi $ (considering $ \\pi $ as a mapping from position to jar label, but for cycle decomposition, we consider the permutation of positions induced by the desired movement).\n\nActually, the standard way: the permutation to sort is $ \\pi $, and we want to apply operations to make it identity. The cycles are in the permutation $ \\pi $.\n\nDefine the permutation $ \\pi: \\{1,2,\\dots,n\\} \\to \\{1,2,\\dots,n\\} $, $ \\pi(i) = $ jar at position $ i $.\n\nWe want to reach $ \\text{id}(i) = i $.\n\nThe cycle decomposition of $ \\pi $ tells us how jars are permuted.\n\nFor example, if $ \\pi = [2,6,5,4,3,1] $, then:\n- $ \\pi(1)=2 $, $ \\pi(2)=6 $, $ \\pi(6)=1 $ → cycle (1 2 6)\n- $ \\pi(3)=5 $, $ \\pi(5)=3 $ → cycle (3 5)\n- $ \\pi(4)=4 $ → fixed\n\nEach cycle of length $ \\ell $ can be sorted in one operation if we take all positions in the cycle and permute them so that each jar goes to its correct position.\n\nAnd since we can combine up to 5 positions in one operation, we can combine multiple cycles into one operation as long as the total number of positions in the cycles is ≤ 5.\n\nSo:\n\n- Let $ C_1, C_2, \\dots, C_k $ be the non-trivial cycles (length ≥ 2), each with size $ \\ell_i $.\n- Use bin packing: pack these cycles into bins of size 5, minimize number of bins.\n- For each bin, collect all positions in the cycles assigned to it.\n- For each such set $ T $, output:\n  - $ |T| $\n  - the positions in $ T $ (in any order)\n  - the target positions: for each position $ i \\in T $, output $ \\pi(i) $ (which is the jar at $ i $, and also the position where it should go)\n\nThis will sort the jars in the minimum number of operations.\n\n**Final Output Format:**\n\n- First line: number of operations = number of bins\n- For each operation:\n  - First line: $ k $\n  - Second line: $ k $ positions (current positions)\n  - Third line: $ k $ target positions (each is $ \\pi(i) $ for the corresponding $ i $)\n\nThis is optimal and correct.","simple_statement":null,"has_page_source":false}