Migrated from Lutece 1006 最长上升子序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一个数的序列$B=(b_1 , b_2 , \cdots , b_S)$，当$b_1< b_2 < \cdots < b_S$ 的时候，我们称这个序列是上升的。对于给定的一个序列$A=(a_1, a_2, \cdots, a_N)$，我们可以得到一些上升的子序列$(a_{i_1}, a_{i_2}, \cdots, a_{i_K})$，这里$1 \le i_1 < i_2 < \cdots <i_K \le N$。比如，对于序列$(1, 7, 3, 5, 9, 4, 8)$，有它的一些上升子序列，如$(1, 7)$, $(3, 4, 8)$等等。这些子序列中最长的长度是$4$，比如子序列$(1, 3, 5, 8)$。

你的任务，就是对于给定的序列，求出最长最小的上升子序列。所谓最长最小的子序列，是指若有多个最长子序列时，存在一个子序列$A=(a_{s_1},a_{s_2},\cdots ,a_{s_k})$，对其它任意最长子序列$B=(a_{t_1},a_{t_2},\cdots ,a_{t_k})$，有前$i-1$个元素相等, 而$a_{s_i}<a_{t_i}$，则$A$是最长最小的上升子序列。

Input

有多组测试数据。输入的第一行是整数$T$（$0<T\le 100$），表示测试数据的组数。每组测试数据占一行，第一个数是序列的长度$N$ ($1 \le N \le 1000$)。紧随其后是序列中的$N$ 个整数，该行每个数后均有一个空格，这些整数的取值范围都在$0$ 到$10000$。该行没有其它多余的符号。

Output

对应每组输入，先输出最长最小的上升子序列长度，再输出最长最小的上升子序列，占一行。每个数后应有一个空格，该行不能有其它多余的符号。

Samples

1
7 1 7 3 5 9 4 8

4 1 3 4 8

Resources

2017 UESTC Training for Dynamic Programming