{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \u003cp\u003eA sequence \u003cvar\u003eS\u003c/var\u003e \u003d {\u003cvar\u003es\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003es\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, ..., \u003cvar\u003es\u003c/var\u003e\u003csub\u003e\u003cvar\u003en\u003c/var\u003e\u003c/sub\u003e} is called \u003ci\u003eheapable\u003c/i\u003e if there exists a binary tree \u003cvar\u003eT\u003c/var\u003e with \u003cvar\u003en\u003c/var\u003e nodes such that every node is labelled with exactly one element from the sequence \u003cvar\u003eS\u003c/var\u003e, and for every non-root node \u003cvar\u003es\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e and its parent \u003cvar\u003es\u003c/var\u003e\u003csub\u003e\u003cvar\u003ej\u003c/var\u003e\u003c/sub\u003e, \u003cvar\u003es\u003c/var\u003e\u003csub\u003e\u003cvar\u003ej\u003c/var\u003e\u003c/sub\u003e ≤ \u003cvar\u003es\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e and \u003cvar\u003ej\u003c/var\u003e \u0026lt; \u003cvar\u003ei\u003c/var\u003e hold. Each element in sequence \u003cvar\u003eS\u003c/var\u003e can be used to label a node in tree \u003cvar\u003eT\u003c/var\u003e only once.\u003c/p\u003e \n \u003cp\u003eChiaki has a sequence \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e\u003cvar\u003en\u003c/var\u003e\u003c/sub\u003e, she would like to decompose it into a minimum number of heapable subsequences.\u003c/p\u003e \n \u003cp\u003eNote that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.\u003c/p\u003e \n 一个数组S\u003d{S1,S2,S3,...,Sn}可以被称为可堆化,如果存在一个二叉树,它的每个节都来自这个数组。对于每个非根节点Si,它的父亲节点Sj,满足Sj≤Si且j \u003c i,且S中的每个元素只会被使用一次。\u003cbr\u003e\n现在Chiaki有一个数组A,他想把它分解成尽可能少的子序列。是的每个子序列都是可堆化的。\n子序列,需要满足在原序列中的相对位置不变,可以不用连续。\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e, indicating the number of test cases. For each test case:\u003c/p\u003e \n \u003cp\u003eThe first line contain an integer \u003cvar\u003en\u003c/var\u003e (1 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e) — the length of the sequence.\u003c/p\u003e \n \u003cp\u003eThe second line contains \u003cvar\u003en\u003c/var\u003e integers \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e\u003cvar\u003en\u003c/var\u003e\u003c/sub\u003e (1 ≤ \u003cvar\u003ea\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e ≤ \u003cvar\u003en\u003c/var\u003e).\u003c/p\u003e \n \u003cp\u003eIt is guaranteed that the sum of all \u003cvar\u003en\u003c/var\u003e does not exceed 2 × 10\u003csup\u003e6\u003c/sup\u003e.\u003c/p\u003e \n第一行一个整数T,表示测试数据组数。\n对于每组测试数据,第一行一个整数n, 表示数组的长度(1 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e) 。\n第二行,n个元素,表示数组中的每个数。\n \u003ch4\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eFor each test case, output an integer \u003cvar\u003em\u003c/var\u003e denoting the minimum number of heapable subsequences in the first line. For the next \u003cvar\u003em\u003c/var\u003e lines, first output an integer \u003cvar\u003eC\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e, indicating the length of the subsequence. Then output \u003cvar\u003eC\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e integers \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e1\u003c/sub\u003e, \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e2\u003c/sub\u003e, ..., \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003eiC\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e\u003c/sub\u003e in increasing order on the same line, where \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003eij\u003c/var\u003e\u003c/sub\u003e means the index of the \u003cvar\u003ej\u003c/var\u003e-th element of the \u003cvar\u003ei\u003c/var\u003e-th subsequence in the original sequence.\u003c/p\u003e \n \n对于每组测试数据,第一行输出一个整数m, 表示最少需要划分的序列数。\u003cbr\u003e\n接下来m行,每行第一个数c,表示一个子序列的长度,接下来c个数,对于到原序列中的下标,表示一个子序列。\u003cbr\u003e\n如果有多个方案,输出任意一个即可。\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e4\n4\n1 2 3 4\n4\n2 4 3 1\n4\n1 1 1 1\n5\n3 2 1 4 1\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e1\n4 1 2 3 4\n2\n3 1 2 3\n1 4\n1\n4 1 2 3 4\n3\n2 1 4\n1 2\n2 3 5\n\u003c/pre\u003e \n \u003ch4"}}]}