LRU Cache

Design a Least Recently Used cache with a fixed capacity supporting get key and put key value. get returns the value or -1 if absent. put inserts or updates a key and, if the capacity is exceeded, evicts the least recently used key. Both get and put count as a use. Both must run in O(1). Print the result of every get.

1 <= capacity <= 3000 1 <= q <= 2 * 10^5