← 返回题目列表

Codeforces · 2001/D

D. 最长最大最小子序列

中文机器翻译题面 查看原题

给定一个整数序列 $$$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]$$$ 是答案。