Design a data structure (with TTL extension)

Design: Implement a data structure with TTL (extend an existing problem) Implement a data structure that supports a set of stack/max-stack operations, and extend it with TTL (time-to-live) expiration. Base requirements Support the following operations: push(x): push element x onto the stack. pop(): remove and return the top element. top(): return the top element without removing it. peekMax(): return the current maximum value in the stack without removing it. popMax(): remove and return the current maximum value; if there are multiple maxima, remove the one closest to the top. TTL extension Add TTL to the structure: Each element is inserted with a TTL (lifespan, e.g., seconds). The system provides current time now (integer timestamp). An element is expired when now >= insert_time + ttl. All operations must ignore expired elements when returning/removing values: Expired elements must not be returned by top/peekMax. pop/popMax should skip and purge expired elements. I/O format (coding-style) Given a sequence of operations; each may include parameters: push x ttl now pop now top now peekMax now popMax now For each operation that returns a value (pop/top/peekMax/popMax), output one line; if no unexpired element exists, output EMPTY. Constraints Number of operations Q: 1 <= Q <= 2 * 10^5 x is a 32-bit integer now is non-decreasing Target amortized complexity close to O(log n) or better Test cases (5) (See Chinese section for full stdin/stdout examples.) Example Input 8 push 5 10 1 top 1 push 1 10 2 peekMax 2 pop 2 pop 2 pop 2 peekMax 2 Output 5 5 1 5 EMPTY EMPTY