Count Increment Calls After a Timestamp

Implement a counter class that supports two operations: increment(timestamp): records one call. timestamp is an integer and is guaranteed to be strictly increasing across calls. query(t): returns how many increment calls have timestamp > t (i.e., the number of calls after the given timestamp t). Design the data structure and implement these APIs. Constraints / Requirements timestamp is an integer within 32-bit range. Timestamps passed to increment are strictly increasing (monotonic). Consider time complexity for both increment and query. Follow-ups (discussion only, no need to code) If increment is called many times per second (high write throughput), how would you design it to handle high frequency while keeping queries efficient? Can you optimize further (e.g., less memory, faster queries, richer range queries)? Example Test Cases Case 1 Ops: inc(1), inc(3), inc(7), query(0), query(3), query(7), query(8) Returns: 3, 1, 0, 0 Case 2 Ops: inc(10), inc(11), inc(12), query(9), query(10), query(11) Returns: 3, 2, 1 Case 3 (single write) Ops: inc(5), query(4), query(5) Returns: 1, 0 Case 4 (sparse timestamps) Ops: inc(1), inc(1000000), inc(2000000), query(999999), query(1000000) Returns: 2, 1 Case 5 (no writes) Ops: query(123) Returns: 0 Example Input inc 1 inc 3 inc 7 query 0 query 3 query 7 query 8 Output 3 1 0 0