2026-01-06 12:16:09 +0300 MSK

class FreqStack:

    def __init__(self):
        self.levels = [None]
        self.last_level = 0
        self.freqs = collections.defaultdict(int)

    def push(self, val: int) -> None:
        freq = self.freqs[val] + 1
        if freq >= len(self.levels):
            self.levels.append([])
        self.levels[freq].append(val)
        self.freqs[val] = freq

    def pop(self) -> int:
        for i in reversed(range(len(self.levels))):
            level = self.levels[i]
            if level:
                val = level.pop()
                self.freqs[val] -= 1
                return val
        raise Exception


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()