给定一个长度为 $$$n$$$ 的数组 $$$a$$$,确定 $$$a$$$ 的按字典顺序最大的 $$$^{\text{∗}}$$$ 子序列$$$^{\text{†}}$$$ $$$s$$$,使得 $$$s$$$ 可以是多边形的边长。
回想一下,$$$s$$$ 可以是多边形的边长当且仅当 $$$|s| \geq 3$$$ 和
$$2 \cdot \max(s_1, s_2, \ldots, s_{|s|}) \lt s_1 + s_2 + \ldots + s_{|s|}.$$
如果不存在这样的子序列$$$s$$$,则打印$$$-1$$$。
$$$^{\text{*}}$$$当且仅当满足以下条件之一时,序列 $$$x$$$ 按字典顺序小于序列 $$$y$$$:
- $$$x$$$ 是 $$$y$$$ 的前缀,但是 $$$x \ne y$$$;
- 在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,序列 $$$x$$$ 的元素比 $$$y$$$ 中的相应元素小。
$$$^{\text{†}}$$$序列 $$$x$$$ 是序列 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过删除多个(可能为零或全部)元素从 $$$y$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$。
保证所有测试用例中 $$$n$$$ 的所有值的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,按以下格式输出答案:
如果答案存在,则输出以下内容。
在第一行中,输出整数 $$$k$$$ ($$$1 \leq k \leq n$$$) — 子序列 $$$s$$$ 的长度。
第二行,输出 $$$k$$$ 整数 $$$s_1, s_2, \ldots, s_k$$$ ($$$1 \leq s_i \leq 10^9$$$, $$$s$$$ 是 $$$a$$$ 的子序列) — 子序列 $$$s$$$。请注意,所需的输出是值,而不是索引。
否则,输出带有整数 $$$-1$$$ 的单行。
示例
输入复制
533 1 241 4 2 361 6 4 5 3 2643 12 99 53 22 479 764 54 73 22 23 1
输出复制
-1 3 4 2 3 4 6 5 3 2 5 43 99 53 22 4 4 54 73 23 1
注意
在第一个测试用例中,没有可以作为多边形边长的子序列。
在第二个测试用例中,有 $$$2$$$ 子序列可以是多边形的边长:$$$1, 4, 2, 3$$$ 和 $$$4, 2, 3$$$。后者是字典顺序上更大的子序列。