Multi-Level Inventory Storage and Retrieval System

Problem: Multi-Level Inventory Storage and Retrieval System Design and implement a class StorageSystem that supports initialization, storing items, and retrieving items. The warehouse has n levels, indexed from 0 to n - 1, where 0 is the top level and n - 1 is the bottom level. Each level has a fixed capacity capacity[i]. Each item has: item_id: a unique string identifier; weight: a positive integer, also the amount of capacity it occupies; timestamp: the time when the operation happens; ttl: time to live. The item expires at timestamp + ttl. To make the recalled interview question directly answerable, this version uses the following clarified rules: At current time t, if t >= timestamp + ttl, the item is expired. It cannot be retrieved and its occupied capacity should be released. store(item_id, weight, timestamp, ttl): Before storing, clean up expired items; Scan levels from top to bottom and place the item into the first level whose remaining capacity is at least weight; Return the level index if successful, otherwise return -1; All item_ids in the input are globally unique. retrieve(timestamp): Before retrieving, clean up expired items; Scan levels from top to bottom; A level is eligible only if its remaining capacity is at least 50% of its total capacity; From the first eligible level that contains unexpired items, retrieve the item with the largest weight; If multiple items have the same weight, retrieve the one stored earlier; if still tied, retrieve the lexicographically smaller item_id; Return the retrieved item_id, or EMPTY if no item can be retrieved. Implement the system. Input Format The first line contains an integer n. The second line contains n integers, the capacities of the levels. The third line contains an integer q, the number of operations. Each of the next q lines is one operation: STORE item_id weight timestamp ttl RETRIEVE timestamp Output Format Print one line for each operation: For STORE, print the level index where the item is stored, or -1 if it fails; For RETRIEVE, print the retrieved item_id, or EMPTY if no item can be retrieved. Constraints 1 <= n <= 100 1 <= q <= 200000 1 <= capacity[i] <= 10^9 1 <= weight <= 10^9 0 <= timestamp <= 10^18 1 <= ttl <= 10^18 item_id consists of letters, digits, and underscores, with length at most 30 Timestamps in the input are non-decreasing All item_ids in the input are globally unique Example Input: 1 10 4 STORE a 3 0 10 STORE b 2 1 10 RETRIEVE 2 RETRIEVE 3 Output: 0 0 a b Example Input 1 10 4 STORE a 3 0 10 STORE b 2 1 10 RETRIEVE 2 RETRIEVE 3 Output 0 0 a b