Problem F
Median
You have found that the AI Overlords use behavioral profiling to flag rebels. They track various uses of supercomputer servers around the world to establish baselines for normal behavior. You’ve intercepted some of their surveillance data and want to determine the data’s median to understand what threshold will trigger an alert, so that you and your fellow rebels can stay under the radar.
Remember that the median of a sorted list of numbers is the number in the middle of the list. If there are an even number of elements, then the median is the mean of the middle $2$ elements.
Input
The first line consists of a single integer, $n$, where $1 \le n \le 10^5$, denoting the ids of your activities the AI overlords have tracked.
The second line consists of $n$ space-separated integers. Each integer is between $0$ and $10^9$ (inclusive).
Output
Output the median of the $n$ integers.
Explanation of sample output
The first sample should output $4$, since the input integers, once sorted, are $1,2,3,4,5,6,7$, and the term in the middle is $4$. The second sample should output $5$ since the input integers, once sorted, are $1,3,7,7$, and the mean of the middle two numbers is $5$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 5 4 3 1 6 7 2 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 3 7 7 |
5 |
