{"trustable":true,"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":"\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\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\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\n\u003ch4\u003eInput\u003c/h4\u003e\n\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\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\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\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\n\u003ch4\u003eOutput\u003c/h4\u003e\n\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\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\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\u003c/td\u003e\n \u003ctd\u003e\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\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n"}}]}