#P18266. Dividing Sequence

Dividing Sequence

Dividing Sequence

题目描述

Alice 从邻居那里得到一个序列 AA。她不喜欢太长的序列,于是打算把它分成两个序列 B,CB,C,再还给邻居。划分须满足:

  • B,CB,C 都是 AA 的子序列,允许其中一个为空。
  • AA 中每个位置的元素恰好分给 B,CB,C 中的一个。两边各自保留这些元素在 AA 中的先后顺序。
  • 按字典序比较,B≤CB\le C。

对于序列 P=(p1,…,pu)P=(p_1,\ldots,p_u) 与 Q=(q1,…,qv)Q=(q_1,\ldots,q_v),PP 的字典序严格小于 QQ,当且仅当满足以下条件之一:

  1. u<vu<v,且 PP 是 QQ 的前缀。
  2. 存在 1≤k≤min⁡(u,v)1\le k\le\min(u,v),前 k−1k-1 个元素均相同,而 pk<qkp_k<q_k。

请找出所有合法划分中,字典序最小的序列 CC。只输出这个最优序列,不需要输出 BB 或各元素的分配方案。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例的第一行一个整数 nn,表示 AA 的长度;第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

每个测试用例输出两行。第一行输出最优 CC 的长度 mm,第二行输出 mm 个整数,即序列 CC。

数据范围

  • 1≤T≤1041\le T\le10^4。
  • 1≤n≤50001\le n\le5000,1≤ai≤1051\le a_i\le10^5。
  • 每个输入文件中所有测试用例的 nn 之和不超过 10410^4。

样例

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