# Problem Link

**Author:** Praveen Dhinwa

**Tester:** Pawel Kacprzak and Misha Chorniy

**Editorialist:** Bhuvnesh Jain

# Difficulty

EASY

# Prerequisites

Greedy, Sorting, Median

# Problem

You are given an array A of size 2 * N consisting of positive integers, where N is an odd number. You can construct an array B from A as follows, B* = max(A[2 * i - 1], A[2 * i]). Consider all permutations of A. Print any one of them which maximises the median of B

# Explanation

The larger elements we have in the array B, the larger will be its median. Since, array B has n elements only, we would like to have the largest n elements of A somehow, go into the array B. Let us assume we have a black box which permutes array A in some manner such that the largest n elements go into array B. Now, what will be the median of array B in such a case? It will be simply the middle element once the array B is sorted.

Now, let us describe the black box now. We see that elements of B are from adjacent elements from A. i.e. they are independent of each other in their selection. Thus, we simply put all the highest n elements in either odd or even positions in array A. This will ensure that are always selected into array B. So, the only requirement is to sort the array A to get the highest n elements. The sorting can be done using mergesort, randomised quick-sort or any inbuilt sort function available.

The above is just one of the methods to construct the array and solve the problem. Multiple solutions to the problem might exist. Feel free to discuss them below.

# Time Complexity

O(n \log{n}) per test case