Stack

class MaxStack:

    def __init__(self):
        self.freq = {}
        self.stack = []
        self.pq = []

    def push(self, x: int) -> None:
        self.freq[x] = self.freq.get(x, 0) + 1
        self.stack.append((x, self.freq[x]))
        heappush(self.pq, (-x, -self.freq[x]))

    def pop(self) -> int:
        x, _ = self.stack.pop()
        self.freq[x] -= 1
        self._clean_up()
        return x

    def top(self) -> int:
        return self.stack[-1][0]

    def peekMax(self) -> int:
        return -self.pq[0][0]

    def popMax(self) -> int:
        x, _ = heappop(self.pq)
        x = -x
        self.freq[x] -= 1
        self._clean_up()
        return x

    def _clean_up(self):
        while len(self.stack) > 0 and self.freq[self.stack[-1][0]] != self.stack[-1][1]:
            self.stack.pop()

        while len(self.pq) > 0 and self.freq[-self.pq[0][0]] != -self.pq[0][1]:
            heappop(self.pq)