Пользовательская структура данных для push, pop и поиска минимума

Мне только что задали следующий вопрос на собеседовании с компанией A:

Вопрос: Разработайте структуру данных, в которой у вас есть 3 операции: push, pop и найти минимум. Вы должны выполнять все 3 операции за постоянное время.

Мой ответ : Я бы использовал связанный список, в котором я могу выполнять вставку и удаление за постоянное время, и я бы использовал дополнительную память для хранения минимум.

Он придумал второй вопрос: если вы выберете минимум, как вы найдете второй минимум? опять же, в постоянное время.

Что бы вы ему сказали?