class FreqStack:
def __init__(self):
self.freq_counter = collections.defaultdict(int)
self.freq_key = collections.defaultdict(list)
self.max_freq = 0
def push(self, val: int) -> None:
self.freq_counter[val] += 1
self.max_freq = max(self.max_freq, self.freq_counter[val])
self.freq_key[self.freq_counter[val]].append(val)
def pop(self) -> int:
val = self.freq_key[self.max_freq].pop()
self.freq_counter[val] -= 1
if not self.freq_key[self.max_freq]:
self.max_freq -= 1
return val