Timed Cache with TTL and LRU Eviction

Problem: Implement a Timed Cache with TTL and LRU Eviction Design and implement a TimedLRUCache that stores key-value pairs. Each key has a TTL assigned when it is inserted or updated. Once expired, the key should be treated as missing. The cache also has a maximum capacity. If inserting a new key makes the number of non-expired keys exceed the capacity, evict one key using the LRU, least recently used, policy. Operations You are given a sequence of operations whose timestamps are non-decreasing: PUT t key value ttl: at time t, insert or update key with value. Its expiration time is t + ttl. If ttl <= 0, the key expires immediately and should not be kept. Updating an existing key makes it the most recently used key. GET t key: query key at time t. If the key does not exist or has expired, print -1. Otherwise, print its value and mark it as most recently used. DEL t key: delete key at time t. No output. SIZE t: print the number of currently non-expired keys at time t. Input Format The first line contains two integers: capacity q Then q lines follow, each describing one operation: PUT t key value ttl GET t key DEL t key SIZE t Output Format Print one line for each GET and SIZE operation. Constraints 1 <= capacity <= 10^5 1 <= q <= 2 * 10^5 Timestamps t are non-decreasing 0 <= t <= 10^18 -10^18 <= ttl <= 10^18 key and value are strings without spaces Aim for amortized or logarithmic time per operation Example Input: 2 7 PUT 0 a 10 5 GET 1 a GET 5 a PUT 6 b 20 2 SIZE 7 SIZE 8 GET 9 b Output: 10 -1 1 0 -1 Example Input 2 7 PUT 0 a 10 5 GET 1 a GET 5 a PUT 6 b 20 2 SIZE 7 SIZE 8 GET 9 b Output 10 -1 1 0 -1