When John and Brus were high school students, they liked to investigate integer sequences.
Once, John wrote down a sequence containing distinct positive integers.
Brus wanted to reorder the elements of the sequence in such a way that the following condition held for all j, where 0 < j < n-1, and n is the number of elements in the sequence:
The (j-1)-th and the (j+1)-th elements of the sequence are either both less than the j-th element or both greater than the j-th element.
In other words, except for the first and last elements, the two immediate neighbors of each element must be either both greater than or both less than that element.
You are given a int sequence containing John's original sequence.
Return the sequence after Brus reordered it.
If there are several possible answers, return the one that comes first lexicographically.
Sequence A comes before sequence B lexicographically if A contains a smaller value at the first index where they differ.