D. 最长最大最小子序列

• 每个测试的时间限制：2 秒
• 内存限制：256 MB

---

题目描述

给定一个整数序列 $a_1, a_2, \dots, 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, \dots, a_n$（$1 \le a_i \le n$）。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

---

输出

对于每个测试用例，按以下格式输出答案：

• 第一行：一个整数 $m$，表示答案序列的长度。
• 第二行：$m$ 个整数 $b_1, b_2, \dots, b_m$，表示答案序列。

---

示例

输入

4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1

输出

3
3 2 1
1
1
3
3 1 2
1
1

---

另一个示例

输入

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
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

---

说明

第一个示例（$a = [3,2,1,3]$）：
$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]$。

第二个示例（$a = [1,1,1,1]$）：
$S = \{[1]\}$，所以答案是 $[1]$。