Maximum-frequency stack

Design a stack-like structure supporting:

• push(val), add val;
• pop(), remove and return the element that appears most frequently so far. If several values tie for the highest frequency, return the one pushed most recently among them.

s = FreqStack()
for v in [5, 7, 5, 7, 4, 5]: s.push(v)   # counts: 5->3, 7->2, 4->1
s.pop() -> 5     # 5 is the most frequent
s.pop() -> 7     # now 5 and 7 tie at 2; 7 was pushed more recently
s.pop() -> 5
s.pop() -> 4

Both operations must run in $O(1)$.