Longest Saw
Contest: Kotlin Heroes: Episode 1
Tags: *special, constructive algorithms

You are given the sequence $$$a_1, a_2, \dots, a_n$$$. You can choose any subset of elements and then reorder them to create a "saw".

The sequence $$$b_1, b_2, \dots, b_m$$$ is called a "saw" if the elements satisfy one of the following series of inequalities: $$$b_1>b_2<b_3>b_4<\dots$$$ or $$$b_1<b_2>b_3<b_4>\dots$$$.

Find the longest saw which can be obtained from a given array.

Note that both the given sequence $$$a$$$ and the required saw $$$b$$$ can contain duplicated (non-unique) values.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases in the input. Then the descriptions of the $$$t$$$ test cases follow. Each test case begins with a line containing integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$). Then a line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) follows.

It's guaranteed that $$$\sum{n}$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print two lines: print the length of the longest saw in the first line, and the saw itself in the second line. If there are several solutions, print any of them.

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

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

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

Editorial:
Let's sort the input array. In any saw, there are two types of elements: minimums and maximums. It is easy to see that you can always take a prefix of the sorted array as minimums, and a suffix of the sorted array as maximums.
Now the only problematic elements in a saw are such values $$$x$$$, that $$$x$$$ belongs to minimums and maximums at the same time. It is easy to see that $$$x$$$ is maximum among minimums and minimum among maximums at the same time. All such values $$$x$$$ should be non-adjacent (non-neighboring) in a saw. Actually, you can use a greedy approach to put all minimums and maximums: just sort all the minimums and put them from left to right in their positions, just sort all the maximums and put them from right to left in their positions. This method "minimizes" the chance to put two $$$x$$$ in the consecutive positions.
So the solution is as follows: you can use a binary search to find the answer. Consider $$$m$$$ is a required length of a saw. We need to check if it is possible to construct such a saw. If $$$m$$$ is even, take $$$m/2$$$ first values from the sorted array of all the elements, take $$$m/2$$$ last values from the sorted array of all the elements. Try to construct a saw: put minimums from left to right and maximums from right to left. Check if is it a saw after it. In case of odd $$$m$$$, you should take care of all the possible cases of a saw topology.
One can prove the greedy algorithm by considering a bipirtite graph (the first part of vertices are minimums, the second part vertices are maximums). Connect two vertices if the corresponding positions are neighboring. You should put all values $$$x$$$ in such a way, that they form an independent set of vertices. Its size can't exeed the size of maximum matching, which is exactly $$$m/2$$$ (rounded down) in this graph. It is easy to see that the greedy approach can put $$$m/2$$$ or less values $$$x$$$ in such a way they are independent. So greedy approach gives an optimal solution.