← 返回题目列表

Codeforces · 2077/D

D. 最大多边形

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

给定一个长度为 $$$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$$$ 的单行。

示例

输入
复制

5
3
3 1 2
4
1 4 2 3
6
1 6 4 5 3 2
6
43 12 99 53 22 4
7
9 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$$$。后者是字典顺序上更大的子序列。