Median of an Array

You are given an array of numbers. Your task is to compute the median of this array. First, sort the array in non-decreasing order. Then, if the total number of elements \(n\) is odd, the median is the middle element, i.e. the \(\frac{n+1}{2}\)-th element (when counting starts from 1). If \(n\) is even, the median is the average of the two middle elements:

\[ \text{median} = \frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2} \]

Print the median to standard output. If the median is an integer, output it without any decimal point; otherwise, print the decimal result.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) (\(n \ge 1\)), which represents the number of elements in the array. The second line contains \(n\) space-separated numbers.

outputFormat

Output the median of the array to standard output (stdout). For an even-length array, if the computed median is a whole number, you can print it as an integer; otherwise, print it as a decimal number.

## sample

7
1 3 3 6 7 8 9

6

</p>