#P18266. Dividing Sequence
Dividing Sequence
Dividing Sequence
题目描述
Alice 从邻居那里得到一个序列 。她不喜欢太长的序列,于是打算把它分成两个序列 ,再还给邻居。划分须满足:
- 都是 的子序列,允许其中一个为空。
- 中每个位置的元素恰好分给 中的一个。两边各自保留这些元素在 中的先后顺序。
- 按字典序比较,。
对于序列 与 , 的字典序严格小于 ,当且仅当满足以下条件之一:
- ,且 是 的前缀。
- 存在 ,前 个元素均相同,而 。
请找出所有合法划分中,字典序最小的序列 。只输出这个最优序列,不需要输出 或各元素的分配方案。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例的第一行一个整数 ,表示 的长度;第二行 个整数 。
输出格式
每个测试用例输出两行。第一行输出最优 的长度 ,第二行输出 个整数,即序列 。
数据范围
- 。
- ,。
- 每个输入文件中所有测试用例的 之和不超过 。
样例
5
5
3 1 2 3 2
3
1 1 2
3
3 3 3
5
1 3 1 3 1
5
2 2 1 3 3
1
3
3
1 1 2
2
3 3
3
1 3 1
4
2 1 3 3