Медиана потока чисел

Числа поступают по одному, и в любой момент нужно быстро назвать медиану всех уже полученных чисел. Функция получает список операций operations и список аргументов values: values[i] — аргументы операции operations[i]. Верните список результатов, по одному на операцию. Вначале набор пуст.

Операции:

• add — аргументы [x]: добавить целое число x в набор; результат null;
• median — аргументов нет ([]): результат — медиана всех чисел, добавленных до этого момента, или null, если набор пуст.

Медиана — средний элемент отсортированного набора, если чисел нечётное количество, и среднее арифметическое двух средних элементов, если чётное (результат дробный, например 1.5). Повторяющиеся числа учитываются каждое отдельно. Операций до 5000, числа по модулю не больше 10⁶; решение должно отвечать на median быстрее, чем сортировкой всего набора.

Пример: ["add", "add", "median", "add", "median"], [[1], [2], [], [3], []] → [null, null, 1.5, null, 2.0].

Источник: задача CodeShare