Find the Median of a List

Given a list of integers, your task is to find the median without using built-in sorting functions. The median of a sequence is defined as follows:

For a sorted sequence \( a_1, a_2, \ldots, a_n \): \[ \text{median} = \begin{cases} a_{\frac{n+1}{2}}, & \text{if } n \text{ is odd;}\\ \frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2}, & \text{if } n \text{ is even.} \end{cases} \]

You are required to implement an efficient algorithm (using the Quickselect approach) to compute the median with optimal performance on average.

inputFormat

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

• The first line contains an integer n, the number of elements in the list.
• The second line contains n space-separated integers.

outputFormat

Output the median value to stdout. If the list has an even number of elements, output the median as a floating point number with one digit after the decimal point.

5
5 3 1 2 4

3