Структура данных для извлечения медианы и 2-го наименьшего элемента в O (lgn)

Мне нужно найти структуру данных, которая удовлетворяет этим требованиям:

• может построить ее из списка из n элементов в O (n)
• вставка элемента занимает O (lgn)
• извлечение медианы занимает O (lgn)
• извлечение 2-го наименьшего элемента занимает O (lgn)

Для первых трех требований это работает: хранить n / 2 наименьших элементов в максимальной куче и n / 2 самых больших в мин кучу. Корни этих куч будут нижней / верхней серединой.

Но я придерживаюсь четвертого требования. Есть идеи?