给定序列 $$$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