P17303 [ICPC 2026 Xi'an I] Would You Make a Convex?

Yuki is the chief judge of the International Convex Polygon Championship (ICPC). He proposed a geometry problem for the competition. However, due to his lack of experience in geometry, he failed to generate correct convex polygon data. To prove his geometric ability, Yuki started playing with sticks again. He has $n$ sticks, where the length of the $i$-th stick is $a_i$. He intends to choose at least $3$ sticks from them such that these sticks can form a non-degenerate convex polygon$^\ast$. However, since Yuki does not know much about geometry, he does not know how to choose the sticks. As a good friend of Yuki, you need to help him find a subset of sticks such that: - The subset contains at least $3$ sticks, and the number of sticks is as large as possible; - For $\textbf{any}$ subset of at least $3$ sticks chosen from this subset, these sticks can form a non-degenerate convex polygon. Or report that no such subset exists. $^\ast$: A non-degenerate convex polygon is a polygon where all side lengths are greater than zero, no three vertices are collinear, and all interior angles are strictly less than $180^\circ$.

This problem contains multiple test cases. The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases. For each test case: - The first line contains a positive integer $n$ $(3 \le n \le 5\cdot10^5)$. - The second line contains $n$ positive integers $a_1, \dots, a_n$ $(1 \le a_i \le 10^9)$. It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^5$.

For each test case, output one line: - If no such subset exists, output a single integer $0$. - If such a subset exists, first output an integer $k$, representing the size of the subset you found, followed by $k$ integers $b_1, \dots, b_k$, representing the lengths of the $k$ sticks in your subset.

For the first test case: - $\{6,2,6\}$ is a valid subset; since $2 + 6 > 6$, these $3$ sticks can form a non-degenerate triangle; it is easy to prove that no larger valid subset exists. - $\{6,6,9\}$ is also a valid subset. For the second test case: - It can be proven that no valid subset exists. For the third test case: - $\{3,4,5,6\}$ is a valid subset; in this case, Yuki has $5$ ways to choose sticks: $\{3,4,5\}, \{3,4,6\}, \{3,5,6\}, \{4,5,6\}, \{3,4,5,6\}$, and each way can form a non-degenerate convex polygon; it is easy to prove that no larger valid subset exists. - $\{3,4,5,6,9\}$ is not a valid subset because the sticks with lengths $3, 4, 9$ cannot form a non-degenerate triangle. - $\{3,5,6\}$ is not a valid subset because there exists a larger valid subset.