Maximum Frequency Stack

Problem Implement FreqStack supporting push(x) and pop(), where pop() removes and returns the most frequent element. If several elements tie for the highest frequency, return the one that was pushed most recently among them.

Input / Output

• Input: a sequence of push/pop operations.
• Output: for each pop, the element removed (one occurrence).

Constraints

• Up to 2·10^4 operations; O(1) amortized per operation is expected (rescanning frequencies on each pop is the naive trap).

Example

• push 5,7,5,7,4,5 → pop()=5 (freq 3); remaining 5:2, 7:2, 4:1 → pop()=7 (tie at freq 2, 7 reached freq 2 more recently); pop()=5; pop()=4.