For this subtask, the question is simply whether or not we have enough ~2~s. If we have at least ~\left\lfloor\frac{N}{2}\right\rfloor~ twos, then we can place them in between the ones, and we have a solution.

For the lexicographically least version, make sure to place the ones as early as possible.

In order to get any valid solution, we should do two things. One, sort and separate the array into the lower half and the upper half. It is optimal to place the lower half in the odd positions because it gives us the best chance of getting a valid array, for instance, if we have 1 1 2, with ~M = 3~, it would be a bad idea to put the upper half in the odd positions, because we would get 1 1 2, which does not satisfy the constraints, but 1 2 1 does.

It suffices to put the lower half at the odd indices and the upper half at the even indices and furthermore, to sort the upper half in decreasing order and the lower half in increasing order. For instance, if ~M = 5~ and we are given 1 2 3 4, then we should make 1 4 2 3, not 1 3 2 4, since the latter does not satisfy the constraints. It can be proven that this algorithm always finds a solution if one exists.

Sort ~a~. We have to place ~a_1~ somewhere, and as we hinted at before, it is optimal to place it first, so that we only have to find one large element to put next to it, not two.

Then, to choose the rest of the elements, it is optimal to always choose the smallest element we have remaining in order to get the lexicographically minimal solution.

For the second subtask, we can use a list and linear search, for ~\mathcal O(N^2)~.

To optimize the solution, we have a few options, the simplest of which is a multiset. We can also binary search and use DSU to check for an element the next free element.

We can actually implement this with just a linked list, storing the sorted elements. We alternate: for odd indices, we take the smallest element in the list. For even indices, we maintain an iterator. At each step, either the element we take is directly after the last even element we took, or it is smaller. This yields an amortized ~\mathcal O(1)~ operation per step.