codeforces#P2077D. Maximum Polygon
Maximum Polygon
Description
Given an array $a$ of length $n$, determine the lexicographically largest$^{\text{∗}}$ subsequence$^{\text{†}}$ $s$ of $a$ such that $s$ can be the side lengths of a polygon.
Recall that $s$ can be the side lengths of a polygon if and only if $|s| \geq 3$ and
$$ 2 \cdot \max(s_1, s_2, \ldots, s_{|s|}) < s_1 + s_2 + \ldots + s_{|s|}. $$
If no such subsequence $s$ exists, print $-1$.
$^{\text{∗}}$A sequence $x$ is lexicographically smaller than a sequence $y$ if and only if one of the following holds:
- $x$ is a prefix of $y$, but $x \ne y$;
- in the first position where $x$ and $y$ differ, the sequence $x$ has a smaller element than the corresponding element in $y$.
$^{\text{†}}$A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deleting several (possibly zero or all) elements.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the array $a$.
It is guaranteed that the total sum of all values of $n$ across all test cases does not exceed $2 \cdot 10^5$.
For each test case, output the answer in the following format:
If the answer exists, output the following.
In the first line, output the integer $k$ ($1 \leq k \leq n$) — the length of the subsequence $s$.
In the second line, output $k$ integers $s_1, s_2, \ldots, s_k$ ($1 \leq s_i \leq 10^9$, $s$ is a subsequence of $a$) — the subsequence $s$. Note that the desired output is the value, not the index.
Otherwise, output a single line with the integer $-1$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the array $a$.
It is guaranteed that the total sum of all values of $n$ across all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output the answer in the following format:
If the answer exists, output the following.
In the first line, output the integer $k$ ($1 \leq k \leq n$) — the length of the subsequence $s$.
In the second line, output $k$ integers $s_1, s_2, \ldots, s_k$ ($1 \leq s_i \leq 10^9$, $s$ is a subsequence of $a$) — the subsequence $s$. Note that the desired output is the value, not the index.
Otherwise, output a single line with the integer $-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
Note
In the first test case, there are no subsequences that can be the side lengths of a polygon.
In the second test case, there are $2$ subsequences that can be the side lengths of a polygon: $1, 4, 2, 3$ and $4, 2, 3$. The latter is the lexicographically larger subsequence.