CF2077D Maximum Polygon

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

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.