D. Make Empty
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of $$$[1, 2, \ldots n]$$$ ($$$n$$$ is even).

You can perform the following operation:

  • Select a subsequence $$$^\dagger$$$ (say $$$t$$$) of length $$$2k$$$ ($$$k$$$ does not need to be the same across operations) such that $$$\max(t_1, t_2, \ldots, t_k) \lt \min(t_{k+1}, t_{k+2}, \ldots, t_{2k})$$$ or $$$\min(t_1, t_2, \ldots, t_k) \gt \max(t_{k+1}, t_{k+2}, \ldots, t_{2k})$$$. Remove $$$t$$$ from $$$p$$$.

You want to make $$$p$$$ empty using the minimum number of operations.

You must also print the subsequence used in each operation, printing the values (not the indices).

$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly, zero or all) elements. For example, $$$[1, 3]$$$, $$$[1, 2, 3]$$$, and $$$[2, 3]$$$ are subsequences of $$$[1, 2, 3]$$$. On the other hand, $$$[3, 1]$$$ and $$$[2, 1, 3]$$$ are not subsequences of $$$[1, 2, 3]$$$.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n$$$ is even) — the length of $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \le n$$$) — the elements of the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the number of operations, $$$x$$$, on the first line. Then print $$$x$$$ lines. On each line, output the length of the subsequence followed by the elements of a valid subsequence. Note that you must print the values, not the indices.

Example
Input
3
2
2 1
4
1 2 3 4
4
2 3 1 4
Output
1
2 2 1 
1
4 1 2 3 4 
2
2 2 4 
2 3 1
Note

In the first test case, we can select $$$t = p$$$ and make $$$p$$$ empty in one operation.

In the second test case, we can again select $$$t = p$$$ in the first operation. We can see that $$$t$$$ is valid because $$$\max(t_1, t_2) = 2$$$ and $$$\min(t_3, t_4) = 3$$$, and $$$2 \lt 3$$$.

In the third test case, it is not possible to make $$$p$$$ empty in one operation because $$$\max(p_1, p_2) \gt \min(p_3, p_4)$$$ and $$$\min(p_1,p_2) \lt \max(p_3,p_4)$$$. In the first operation, we can select $$$t = [2, 4]$$$. On removing $$$t$$$ from $$$p$$$, we get $$$p = [3, 1]$$$. So, we can select $$$t = p$$$ in the second operation.