DMOPC '19 Contest 2 P1 - Box and Whiskers - DMOJ: Modern Online Judge

DMOPC '19 Contest 2 P1 - Box and Whiskers

Points: 5

Time limit: 2.0s

Memory limit: 64M

Author:

Problem type

Veshy is struggling in data management class. Veshy forgot how to make a box and whisker plot, so he wants you to tell him the important values to make the plot of the $N$ ~N~ data points $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~. He gives you: the minimum, maximum, $Q_1$ ~Q_1~ (Quartile 1 or median of the first $\left\lfloor\frac{N}{2}\right\rfloor$ ~\left\lfloor\frac{N}{2}\right\rfloor~ elements), $Q_2$ ~Q_2~ (Quartile 2 or median of the entire data), and $Q_3$ ~Q_3~ (Quartile 3 or median of the last $\left\lfloor\frac{N}{2}\right\rfloor$ ~\left\lfloor\frac{N}{2}\right\rfloor~ elements) of the sorted list.
For example, if the data set was $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ ~\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}~, the important values in their respective order would be: 1, 10, 3, 5.5, 8
Another example, if the data set was $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$ ~\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}~, the important values in their respective order would be: 1, 11, 3, 6, 9

Constraints

In all tests,
$5 \le N \le 10^5$ ~5 \le N \le 10^5~
$0 \le a_i \le 10^6$ ~0 \le a_i \le 10^6~
All numbers are guaranteed to be whole numbers.

Input Specification

The first line contains a number, $N$ ~N~, the number of data points.
The second line contains $N$ ~N~ numbers separated by spaces, the data points Veshy gives you: $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~
Note: the data points are not guaranteed to be in sorted order.

Output Specification

Output the minimum, maximum, $Q_1$ ~Q_1~, $Q_2$ ~Q_2~, $Q_3$ ~Q_3~, in that order separated by spaces on a single line.
Note: your answer will be judged as correct if it is within an absolute or relative error of $10^{-6}$ ~10^{-6}~.