Реализуйте кэш вместимостью capacity с вытеснением давно неиспользуемых записей (LRU). Операции заданы списком ops, каждая - тройка [код, ключ, значение]:
- код 0 - put(ключ, значение): добавляет или обновляет запись; если после этого записей больше capacity, вытесняется самая давно использованная;
- код 1 - get(ключ) (значение в тройке игнорируется): возвращает значение или -1, если ключа нет.
И put, и get считаются «использованием» записи (обновляют её давность). Верните список результатов всех get в порядке вызова.
Каждая операция должна работать за O(1) - линейный поиск давности по всем записям на каждый вызов слишком медленный на длинной последовательности.