Find the Median

You are given an array of integers. Your task is to find the median of the array by first sorting the array using a custom implementation of the quicksort algorithm (i.e., without using any built-in sorting functions).

For an array with \( n \) elements, after sorting in non-decreasing order, the median is defined as the element at index \( \lfloor n/2 \rfloor \) (0-indexed). For example, if \( n \) is odd, this is the middle element; if \( n \) is even, for this problem, return the lower middle element.

Note: You must implement your own sorting algorithm (e.g., quicksort) to sort the array.

inputFormat

The first line contains a single integer \( n \), the number of elements in the array.

The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single integer: the median of the array.

## sample

5
3 1 4 1 5

3

</p>