Rearrange Array by Median

You are given an array of integers. Your task is to rearrange the array such that the median element appears at the first position, and the remaining elements are arranged in increasing order based on their absolute distance from the median.

For the purpose of this problem, the median is defined as follows:

• If the array has an odd number of elements, the median is the middle element in the sorted order.
• If the array has an even number of elements, the median is defined as the \(\left(\frac{n}{2}\right)\)th smallest element (i.e. the lower median when elements are 1-indexed).

The rearrangement is performed by calculating \(|x - m|\) for every element \(x\) in the array where \(m\) is the median, and then sorting the array by these distances in increasing order. In case of a tie (i.e. two elements with the same distance), they are ordered by their natural value ordering.

If the input array is empty, simply output an empty array.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer \(n\), denoting the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), the second line may be empty.

outputFormat

Print to standard output (stdout) the rearranged array in a single line with the elements separated by a single space. If the array is empty, print nothing.

5
3 1 2 5 4

3 2 4 1 5