По логу сервиса собраны времена обработки $n$ запросов в микросекундах. Требуется посчитать перцентили $p50$, $p95$ и $p99$.
Определение
Пусть $x_0 \le x_1 \le \dots \le x_{n-1}$ — отсортированные значения. Перцентиль уровня $p$ определяется линейной интерполяцией между соседними порядковыми статистиками:
$$h = \frac{(n-1) \cdot p}{100}, \qquad P(p) = x_{\lfloor h \rfloor} + (h - \lfloor h \rfloor)\cdot\left(x_{\lceil h \rceil} - x_{\lfloor h \rfloor}\right)$$
Это то же определение, что использует numpy.percentile с методом по умолчанию.
Формат ввода
В первой строке — число запросов $n$ ($1 \le n \le 200000$).
Во второй строке — $n$ целых чисел $x_i$ ($0 \le x_i \le 10000000$), времена обработки в микросекундах.
Формат вывода
Три числа — $p50$, $p95$, $p99$ — в одной строке, разделённые пробелами.
Ответ считается верным, если он отличается от эталонного не более чем на $10^{-6}$ абсолютно или относительно.
Замечание
Округление до ближайшей порядковой статистики (метод nearest-rank) даёт другой результат и не принимается.