{"problem":{"name":"C. 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":"CF844C"},"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 distinct integers.  \nLet $ P = \\{1, 2, \\dots, n\\} $ be the set of indices.  \n\nA *subsequence partition* is a collection of disjoint non-empty index sets $ S_1, S_2, \\dots, S_k \\subseteq P $ such that $ \\bigcup_{i=1}^k S_i = P $.  \n\nFor each subsequence $ S_i $, let $ A|_{S_i} $ denote the subsequence of $ A $ indexed by $ S_i $. Let $ \\text{sort}(A|_{S_i}) $ denote the sequence $ A|_{S_i} $ sorted in increasing order.  \n\nDefine the *reconstructed sequence* after sorting all subsequences as the sequence $ B = (b_1, b_2, \\dots, b_n) $, where for each position $ j \\in P $, if $ j \\in S_i $, then $ b_j $ is the element of $ \\text{sort}(A|_{S_i}) $ that occupies the same relative position in $ S_i $ as $ j $ does in the sorted order of $ S_i $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ a_i \\in \\mathbb{Z} $, $ -10^9 \\le a_i \\le 10^9 $, and all $ a_i $ are distinct.  \n3. The reconstructed sequence $ B $ must satisfy $ b_1 \\le b_2 \\le \\dots \\le b_n $ (i.e., non-decreasing).  \n\n**Objective**  \nMaximize $ k $, the number of subsequences in the partition, such that the reconstructed sequence $ B $ is non-decreasing.  \n\nOutput:  \n- The maximum $ k $.  \n- For each $ i \\in \\{1, \\dots, k\\} $:  \n  - The size $ c_i = |S_i| $,  \n  - The set of indices $ S_i = \\{l_1, l_2, \\dots, l_{c_i}\\} \\subseteq P $, in any order.  \n\n**Note**: The partition must cover all indices exactly once.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF844C","tags":["dfs and similar","math"],"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"}}