Design an LFU cache

Design a fixed-capacity key-value cache supporting:

• get(key), return the value or -1 if absent;
• put(key, value), insert or update; when full, evict the least frequently used entry. If several keys share the lowest use-count, evict the one that was least recently used among them.

Every get and every put counts as one "use" of that key.

c = LFUCache(2)
c.put(1, 1); c.put(2, 2)
c.get(1) -> 1          # key 1 now has count 2, key 2 has count 1
c.put(3, 3)            # evicts key 2 (lowest count)
c.get(2) -> -1

Both operations must run in $O(1)$.