CF1097E.Egor and an RPG game

One Saturday afternoon Egor was playing his favorite RPG game. While discovering new lands and territories, he came across the following sign:

Egor is a passionate player, but he is an algorithmician as well. That's why he instantly spotted four common letters in two words on the sign above — if we permute the letters "R", "E", "G", "O" from the first word, we can obtain the letters "O", "G", "R", "E". Egor got inspired by the sign and right away he came up with a problem about permutations.

You are given a permutation of length $n$. You have to split it into some non-empty subsequences so that each element of the permutation belongs to exactly one subsequence. Each subsequence must be monotonic — that is, either increasing or decreasing.

Sequence is called to be a subsequence if it can be derived from permutation by deleting some (possibly none) elements without changing the order of the remaining elements.

The number of subsequences should be small enough — let $f(n)$ be the minimum integer $k$ such that every permutation of length $n$ can be partitioned into at most $k$ monotonic subsequences.

You need to split the permutation into at most $f(n)$ monotonic subsequences.

某个星期六下午，伊戈尔正在玩他最喜爱的角色扮演游戏。在探索新大陆和新领地时，他遇到了如下标志：

伊戈尔是一位狂热的玩家，同时也是一名算法学家。因此，他立刻注意到标志上两个单词中存在四个常见字母——若将第一个单词中的字母 “R”、“E”、“G”、“O” 重新排列，便可得到第二个单词中的字母 “O”、“G”、“R”、“E”。受该标志启发，伊戈尔立即构思出一个关于排列的问题。

给定一个长度为 $n$ 的排列。你需要将其划分为若干个非空子序列，使得排列中的每个元素恰好属于其中一个子序列。每个子序列必须是单调的——即要么严格递增，要么严格递减。

若一个序列可通过从原排列中删除若干（可能为零）个元素、且不改变剩余元素的相对顺序而得到，则称其为一个子序列。

子序列的数目应尽可能少——记 $f(n)$ 为满足如下条件的最小整数 $k$：任意长度为 $n$ 的排列均可被划分为至多 $k$ 个单调子序列。

你需要将给定排列划分为至多 $f(n)$ 个单调子序列。

The first line contains one integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

You can only use $t = 1$ in hacks.

Next, descriptions of $t$ test cases come, each of them in the following format.

The first line of a single test case contains one integer $n$ ($1 \leq n \leq 10^5$) — the length of the permutation. The second line contains $n$ distinct integers $a_i$ ($1 \leq a_i \leq n$) — the permutation itself.

The sum of the values of $n$ over all test cases doesn't exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）—— 测试用例的数量。

在 hack 中，你只能使用 $t = 1$。

接下来是 $t$ 个测试用例的描述，每个测试用例的格式如下：

单个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 排列的长度。第二行包含 $n$ 个互不相同的整数 $a_i$（$1 \leq a_i \leq n$）—— 排列本身。

所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case print the answer in the following format:

In the first line print $k$ ($1 \leq k \leq f(n)$) — the number of the subsequences in the partition. In the next $k$ lines, print the descriptions of found subsequences. Each description should start with a number $l_i$ ($1 \leq l_i \leq n$) — the length of the corresponding subsequence, followed by $l_i$ integers — the values of this subsequence in the order in which they occur in the permutation.

Each subsequence you output must be either increasing or decreasing.

In case there are multiple possible answers, print any of them.

对每个测试用例，按以下格式输出答案：

第一行输出 $k$（$1 \leq k \leq f(n)$）—— 即划分中子序列的个数。接下来 $k$ 行，输出所找到的各子序列的描述。每条描述应以一个整数 $l_i$（$1 \leq l_i \leq n$）开头，表示该子序列的长度，随后是 $l_i$ 个整数 —— 即该子序列中各元素在原排列中出现的顺序。

你输出的每个子序列必须是严格递增或严格递减的。

若存在多种可能的答案，输出任意一种即可。

In the example, we can split:

• $[4, 3, 1, 2]$ into $[4, 3, 1]$, $[2]$
• $[4, 5, 6, 1, 3, 2]$ into $[4, 1]$, $[5, 6]$ and $[3, 2]$
• $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ into $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$

Surely, there are many more answers possible.

在示例中，我们可以进行如下划分：

• $[4, 3, 1, 2]$ 划分为 $[4, 3, 1]$ 和 $[2]$
• $[4, 5, 6, 1, 3, 2]$ 划分为 $[4, 1]$、$[5, 6]$ 和 $[3, 2]$
• $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ 划分为 $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$

当然，还存在许多其他可能的划分方式。