structures

class StackWithMaxElement:
    def __init__(self):
        self.items = []
        self.max = []

    def push(self, item):
        self.items.append(int(item))
        if len(self.max) == 0:
            self.max.append(item)
        elif item >= self.max[-1]:
            self.max.append(item)

    def pop(self):
        tmp = self.items.pop()
        if tmp == self.max[-1]:
            self.max.pop()
        return tmp

    def get_max(self):
        return self.max[-1]

    def is_empty(self):
        return len(self.items) == 0

    def clear(self):
        self.items.clear()


class QueueWithMaxElement:
    def __init__(self):
        self.stack1 = StackWithMaxElement()
        self.stack2 = StackWithMaxElement()

    def push(self, item):
        self.stack1.push(item)

    def pop(self):
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())
        return self.stack2.pop()

    def get_max(self):
        if self.stack1.is_empty():
            return self.stack2.get_max()
        elif self.stack2.is_empty():
            return self.stack1.get_max()
        else:
            return max(self.stack1.get_max(), self.stack2.get_max())