D. Longest Max Min Subsequence
brute force; constructive algorithms; data structures; greedy; implementation
You are given an integer sequence \(a_1, a_2, \ldots, a_n\). Let \(S\) be the set of all possible non-empty subsequences of \(a\) without duplicate elements. Your goal is to find the longest sequence in \(S\). If there are multiple of them, find the one that minimizes lexicographical order after multiplying terms at odd positions by \(-1\).For example, given \(a = [3, 2, 3, 1]\), \(S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}\). Then \([2, 3, 1]\) and \([3, 2, 1]\) would be the longest, and \([3, 2, 1]\) would be the answer since \([-3, 2, -1]\) is lexicographically smaller than \([-2, 3, -1]\).A sequence \(c\) is a subsequence of a sequence \(d\) if \(c\) can be obtained from \(d\) by the deletion of several (possibly, zero or all) elements.A sequence \(c\) is lexicographically smaller than a sequence \(d\) if and only if one of the following holds: \(c\) is a prefix of \(d\), but \(c \ne d\); in the first position where \(c\) and \(d\) differ, the sequence \(c\) has a smaller element than the corresponding element in \(d\).
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 5 \cdot 10^4\)). The description of the test cases follows.The first line of each test case contains an integer \(n\) (\(1 \le n \le 3 \cdot 10^5\)) — the length of \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — the sequence \(a\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(3 \cdot 10^5\).
For each test case, output the answer in the following format:Output an integer \(m\) in the first line — the length of \(b\).Then output \(m\) integers \(b_1, b_2, \ldots, b_m\) in the second line — the sequence \(b\).
In the first example, \(S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\}\). Among them, \([2, 1, 3]\) and \([3, 2, 1]\) are the longest and \([-3, 2, -1]\) is lexicographical smaller than \([-2, 1, -3]\), so \([3, 2, 1]\) is the answer.In the second example, \(S = \{[1]\}\), so \([1]\) is the answer.