{"problem":{"name":"A. Sorting by Subsequences","description":{"content":"You are given a sequence _a_1, _a_2, ..., _a__n_ consisting of **different** integers. It is required to split this sequence into the **maximum** number of subsequences such that after sorting integer","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF843A"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence _a_1, _a_2, ..., _a__n_ consisting of **different** integers. It is required to split this sequence into the **maximum** number of subsequences such that after sorting integers in each of them in increasing order, the total sequence also will be sorted in increasing order.\n\nSorting integers in a subsequence is a process such that the numbers included in a subsequence are ordered in increasing order, and the numbers which are not included in a subsequence don't change their places.\n\nEvery element of the sequence must appear in exactly one subsequence.\n\n## Input\n\nThe first line of input data contains integer _n_ (1 ≤ _n_ ≤ 105) — the length of the sequence.\n\nThe second line of input data contains _n_ different integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the elements of the sequence. It is guaranteed that all elements of the sequence are distinct.\n\n## Output\n\nIn the first line print the maximum number of subsequences _k_, which the original sequence can be split into while fulfilling the requirements.\n\nIn the next _k_ lines print the description of subsequences in the following format: the number of elements in subsequence _c__i_ (0 < _c__i_ ≤ _n_), then _c__i_ integers _l_1, _l_2, ..., _l__c__i_ (1 ≤ _l__j_ ≤ _n_) — indices of these elements in the original sequence.\n\nIndices could be printed in any order. Every index from 1 to _n_ must appear in output **exactly once**.\n\nIf there are several possible answers, print any of them.\n\n[samples]\n\n## Note\n\nIn the first sample output:\n\nAfter sorting the first subsequence we will get sequence 1 2 3 6 5 4.\n\nSorting the second subsequence changes nothing.\n\nAfter sorting the third subsequence we will get sequence 1 2 3 4 5 6.\n\nSorting the last subsequence changes nothing.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个由*不同*整数组成的序列 #cf_span[a1, a2, ..., an]。要求将该序列划分为*最大*数量的子序列，使得将每个子序列中的整数按升序排序后，整个序列也会按升序排列。\n\n对一个子序列排序是指：该子序列中的数字按升序排列，而未包含在该子序列中的数字保持原位置不变。\n\n序列中的每个元素必须恰好属于一个子序列。\n\n输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列的长度。\n\n第二行包含 #cf_span[n] 个不同的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 序列的元素。保证序列中所有元素互不相同。\n\n第一行输出最大可能的子序列数量 #cf_span[k]，使得原序列能按要求划分为 #cf_span[k] 个子序列。\n\n接下来的 #cf_span[k] 行，每行描述一个子序列：首先输出该子序列的元素个数 #cf_span[ci] (#cf_span[0 < ci ≤ n])，然后输出 #cf_span[ci] 个整数 #cf_span[l1, l2, ..., lci] (#cf_span[1 ≤ lj ≤ n]) —— 这些元素在原序列中的下标。\n\n下标可以按任意顺序输出。从 #cf_span[1] 到 #cf_span[n] 的每个下标必须在输出中恰好出现一次。\n\n如果有多个可能的答案，输出任意一个即可。\n\n在第一个样例输出中：\n\n对第一个子序列排序后，得到序列 #cf_span[1 2 3 6 5 4]。\n\n对第二个子序列排序不改变任何内容。\n\n对第三个子序列排序后，得到序列 #cf_span[1 2 3 4 5 6]。\n\n对最后一个子序列排序不改变任何内容。\n\n## Input\n\n输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列的长度。第二行包含 #cf_span[n] 个不同的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 序列的元素。保证序列中所有元素互不相同。\n\n## Output\n\n第一行输出最大可能的子序列数量 #cf_span[k]，使得原序列能按要求划分为 #cf_span[k] 个子序列。接下来的 #cf_span[k] 行，每行描述一个子序列：首先输出该子序列的元素个数 #cf_span[ci] (#cf_span[0 < ci ≤ n])，然后输出 #cf_span[ci] 个整数 #cf_span[l1, l2, ..., lci] (#cf_span[1 ≤ lj ≤ n]) —— 这些元素在原序列中的下标。下标可以按任意顺序输出。从 #cf_span[1] 到 #cf_span[n] 的每个下标必须在输出中恰好出现一次。如果有多个可能的答案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n在第一个样例输出中：对第一个子序列排序后，得到序列 #cf_span[1 2 3 6 5 4]。对第二个子序列排序不改变任何内容。对第三个子序列排序后，得到序列 #cf_span[1 2 3 4 5 6]。对最后一个子序列排序不改变任何内容。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of $ n $ distinct integers.  \nLet $ \\sigma : \\{1, \\dots, n\\} \\to \\{1, \\dots, n\\} $ be the permutation such that $ a_{\\sigma(i)} $ is the $ i $-th smallest element in $ A $, i.e., $ a_{\\sigma(1)} < a_{\\sigma(2)} < \\dots < a_{\\sigma(n)} $.  \n\nA *subsequence partition* is a collection of disjoint non-empty index sets $ \\{I_1, I_2, \\dots, I_k\\} $ such that $ \\bigcup_{j=1}^k I_j = \\{1, 2, \\dots, n\\} $.  \nFor each $ I_j $, let $ S_j $ denote the sorted sequence of $ \\{a_i \\mid i \\in I_j\\} $ in increasing order.  \n\nThe partition is *valid* if, when each subsequence $ I_j $ is sorted internally, the resulting global sequence (with elements from different subsequences placed in their original relative positions) is sorted in increasing order.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ a_i \\in \\mathbb{Z} $, $ -10^9 \\leq a_i \\leq 10^9 $, all $ a_i $ are distinct.  \n\n**Objective**  \nFind the *maximum* number $ k $ of subsequences in a valid partition of $ \\{1, \\dots, n\\} $, and output one such partition achieving this maximum.\n\n**Key Insight (Formal Characterization)**  \nA partition into $ k $ subsequences is valid if and only if, for each $ j \\in \\{1, \\dots, k\\} $, letting $ I_j = \\{i_1, i_2, \\dots, i_{c_j}\\} $ with $ i_1 < i_2 < \\dots < i_{c_j} $, the following holds:  \n> The set of values $ \\{a_i \\mid i \\in I_j\\} $ is exactly the set of values that should appear in the final sorted sequence at the positions $ \\{\\sigma^{-1}(i) \\mid i \\in I_j\\} $, and no value from $ I_j $ should be \"out of place\" relative to values from other subsequences.\n\nEquivalently, the maximum number of valid subsequences is equal to the number of *left-to-right maxima* in the permutation defined by the positions of the sorted elements.\n\nMore precisely:  \nLet $ p $ be the permutation where $ p(i) $ is the position (1-indexed) of the $ i $-th smallest element in $ A $.  \nThen, the maximum number of subsequences is the number of indices $ i \\in \\{1, \\dots, n\\} $ such that:  \n$$\n\\max\\{p(1), p(2), \\dots, p(i)\\} = p(i)\n$$\n\nEach such index marks the end of a subsequence. The subsequences are formed by grouping indices between consecutive such maxima.\n\n**Output Format**  \n- First line: $ k $, the maximum number of subsequences.  \n- Next $ k $ lines: for each subsequence, output $ c_j $ (its size), followed by the original indices (1-based) of its elements, in any order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF843A","tags":["dfs and similar","dsu","implementation","math","sortings"],"sample_group":[["6\n3 2 1 6 5 4","4\n2 1 3\n1 2\n2 4 6\n1 5"],["6\n83 -75 -49 11 37 62","1\n6 1 2 3 4 5 6"]],"created_at":"2026-03-03 11:00:39"}}