给定一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。令 $$$S$$$ 为 $$$a$$$ 的所有可能非空子序列的集合,且不包含重复元素。您的目标是找到 $$$S$$$ 中最长的序列。如果有多个,则将奇数位置的术语乘以 $$$-1$$$ 后找到使字典顺序最小化的一个。
例如,给定 $$$a = [3, 2, 3, 1]$$$,$$$S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}$$$。那么 $$$[2, 3, 1]$$$ 和 $$$[3, 2, 1]$$$ 将是最长的,$$$[3, 2, 1]$$$ 将是答案,因为 $$$[-3, 2, -1]$$$ 按字典顺序小于 $$$[-2, 3, -1]$$$。
如果 $$$c$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$d$$$ 获得,则序列 $$$c$$$ 是序列 $$$d$$$ 的子序列。
当且仅当满足以下条件之一时,序列 $$$c$$$ 按字典顺序小于序列 $$$d$$$:
- $$$c$$$ 是 $$$d$$$ 的前缀,但 $$$c \ne d$$$;
- 在 $$$c$$$ 和 $$$d$$$ 不同的第一个位置,序列 $$$c$$$ 的元素比 $$$d$$$ 中的相应元素小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 序列 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,按以下格式输出答案:
第一行输出一个整数$$$m$$$——$$$b$$$的长度。
然后在第二行输出 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ — 序列 $$$b$$$。
示例
输入 #1
4 4 3 2 1 3 4 1 1 1 1 9 3 2 1 3 2 1 3 2 1 1 1
输出 #1
3 3 2 1 1 1 3 3 1 2 1 1
输入 #2
10 2 1 2 10 5 2 1 7 9 7 2 5 5 2 2 1 2 10 2 2 8 7 7 9 8 1 9 6 9 9 1 7 5 8 5 6 4 1 3 3 3 3 6 1 6 4 4 6 5 6 3 4 4 5 3 3 10 4 1 4 5 4 5 10 1 5 1 7 1 2 1 3 2 4 6
输出 #2
2 1 2 5 5 1 9 7 2 2 1 2 6 2 7 9 8 1 6 7 9 1 7 5 8 6 4 1 3 4 1 4 6 5 3 4 5 3 4 5 4 10 1 5 2 1 3 4 6
注意
在第一个示例中,$$$S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\}$$$。其中,$$$[2, 1, 3]$$$和$$$[3, 2, 1]$$$是最长的,而$$$[-3, 2, -1]$$$在字典上比$$$[-2, 1, -3]$$$小,所以$$$[3, 2, 1]$$$就是答案。
在第二个示例中,$$$S = \{[1]\}$$$,因此 $$$[1]$$$ 是答案。