Transform Array Around Median

ID: 24469

Type: Default

1000ms

256MiB

You are given an array of N distinct integers. Your task is to transform the array as follows: First, find the median element of the array. Here, if the array size is even, then the median is defined as the lower middle element when the array is sorted in ascending order.

Once the median is determined, partition the array into two parts:

All elements less than the median, sorted in ascending order.
All elements greater than the median, sorted in descending order.

Finally, combine these two sorted arrays by placing the median between them. Formally, if med is the median, then the result is:

$$\text{result} = (sorted(\{x: xmed\})) $$

For example, given the array [3, 1, 4, 2, 5], the transformed array is [1, 2, 3, 5, 4].

inputFormat

The first line contains an integer N representing the size of the array.

The second line contains N space-separated integers representing the elements of the array.

Note: All numbers in the array are distinct.

outputFormat

Output the transformed array in a single line. The elements should be space-separated.

## sample

5
3 1 4 2 5

1 2 3 5 4

</p>

#K15946. Transform Array Around Median

Transform Array Around Median