Implement a recent-use eviction cache

Design a fixed-capacity key-value cache that removes the least recently accessed item when it becomes full. Implement a class with the following operations: - `Cache(int capacity)`: Initialize the cache with a positive capacity. - `int get(int key)`: Return the value associated with `key` if it exists; otherwise return `-1`. A successful `get` marks the key as the most recently used item. - `void put(int key, int value)`: Insert or update the value for `key`. If the cache is already at capacity and the key does not already exist, evict the least recently used key before inserting. Updating an existing key also marks it as the most recently used item. Requirements: - Both `get` and `put` should run in average `O(1)` time. - Keys and values are integers. Example behavior: 1. `Cache(2)` 2. `put(1, 10)` 3. `put(2, 20)` 4. `get(1)` returns `10` and makes key `1` most recently used. 5. `put(3, 30)` evicts key `2` because it is the least recently used. 6. `get(2)` returns `-1`.