← 返回题目列表

Codeforces · 1170/H

H. 最长的锯

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

给定序列 $$$a_1, a_2, \dots, a_n$$$。您可以选择元素的任何子集,然后对它们重新排序以创建“锯子”。

如果元素满足以下一系列不等式之一,则序列 $$$b_1, b_2, \dots, b_m$$$ 称为“锯子”:$$$b_1>b_2<b_3>b_4<\dots$$$ 或 $$$b_1<b_2>b_3<b_4>\dots$$$。

找出从给定数组中可以获得的最长的锯。

请注意,给定序列 $$$a$$$ 和所需的锯 $$$b$$$ 都可以包含重复(非唯一)值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例的描述。每个测试用例都以包含整数 $$$n$$$ 的行开始 ($$$1 \le n \le 2\cdot10^5$$$)。接下来是包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) 的行。

保证 $$$\sum{n}$$$ 不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印两行:在第一行中打印最长锯的长度,在第二行中打印锯本身。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
10
10 9 8 7 6 5 4 3 2 1
7
1 2 2 2 3 2 2
3
100 100 100

输出 #1

10
1 6 2 7 3 8 4 9 5 10 
4
2 1 3 2 
1
100