Longest Max Min Subsequence
Contest: Codeforces Round 967 (Div. 2)
Difficulty rating: 1900
Tags: 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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1

Example output:
3
3 2 1
1
1
3
3 1 2
1
1

Example input:
10
2
1 2
10
5 2 1 7 9 7 2 5 5 2
2
1 2
10
2 2 8 7 7 9 8 1 9 6
9
9 1 7 5 8 5 6 4 1
3
3 3 3
6
1 6 4 4 6 5
6
3 4 4 5 3 3
10
4 1 4 5 4 5 10 1 5 1
7
1 2 1 3 2 4 6

Example output:
2
1 2
5
5 1 9 7 2
2
1 2
6
2 7 9 8 1 6
7
9 1 7 5 8 6 4
1
3
4
1 4 6 5
3
4 5 3
4
5 4 10 1
5
2 1 3 4 6

Editorial:
Consider subtask:
Let's ignore the constraint where $$$b$$$ should be lexicographically smallest. How can we find the length of $$$b$$$?
Apparently, it is the number of distinct elements in $$$a$$$. Let's call it $$$k$$$.
Construct $$$b$$$ from left to right without worsening the answer:
Now we know how to find the maximum possible length of $$$b$$$. Let's try to construct $$$b$$$ from left to right without worsening the answer, and greedily minimize its lexicographical order. Assume we pick $$$a_i$$$ as the $$$j$$$-th element in $$$b$$$, then there should be $$$k - j$$$ distinct elements in the subarray $$$a[i + 1, n]$$$ after deleting all elements that appear in the subarray $$$b[1, j]$$$.
Assume we already construct $$$b_1, b_2, \ldots, b_j$$$ where $$$b_j = a_i$$$ and we want to find $$$b_{j + 1}$$$, and let $$$l_x$$$ be the last position where $$$x$$$ occurs in the subarray $$$a[i + 1, n]$$$ or $$$\infty$$$ if it doesn't exist, then we can choose anything in $$$a[i + 1, \min\limits_{1 \le x \le n}(l_x)]$$$. And to minimize lexicographical order, we need to choose the maximum element in it if $$$(j + 1)$$$ is odd, or the minimum element otherwise. If there are multiple of them, choose the leftmost one of them is optimal since we would have a longer suffix of $$$a$$$ for future construction.
Then observe for the candidate window (i.e. $$$a[i + 1, \min\limits_{1 \le x \le n}(l_x)]$$$), its left bound and right bound is non-decreasing, so we can use two priority queues to maintain all possible candidates by storing $$$(a_{pos}, pos)$$$, and another priority queue to maintain all $$$l_x > i$$$. And the total time complexity is $$$O(nlgn)$$$.