"""
implement a standard lifo stack with the added functionality of getting the max value
all operations should be O(1)
"""


class MaxStack:

    def __init__(self, iterable=()):
        self._q = []
        self._max = []
        for v in iterable:
            self.push(v)

    def push(self, v):
        if self.empty():
            self._max.append(v)
        else:
            self._max.append(max(v, self.peek()))
        self._q.append(v)

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

    def empty(self):
        return len(self._q) == 0

    def peek(self):
        return self._q[-1]

    def pop(self):
        self._max.pop()
        return self._q.pop()