Max Stack

Design a stack-like container called MaxStack that supports the usual push/pop operations from the top, but also lets you query and remove the maximum value currently stored, regardless of where it sits in the stack.

Implement a class that supports the following operations:

• push(x): push integer x onto the top of the stack. Returns nothing.
• pop(): remove and return the element at the top of the stack.
• top(): return (without removing) the element at the top of the stack.
• peekMax(): return (without removing) the maximum element currently in the stack.
• popMax(): remove and return the maximum element currently in the stack. If there is more than one element equal to the maximum, remove the one that is closest to the top of the stack (i.e., the most recently pushed among the ties).

You are given a sequence of operation names paired with their argument lists (empty list for operations that take no arguments). Simulate them in order and return a list containing the result of each operation, using None for operations that don't produce a return value (push).

For example, if you push 5, then 1, then 5, and call popMax(), the second 5 (the one pushed last) is removed, since it is nearer the top than the first one.

Examples

Example 1:

Input: ops = [push(5), push(1), push(5), popMax(), top(), peekMax(), pop(), top()]

Output: [null,null,null,5,1,5,1,5]

Explanation:

After pushing 5, 1, 5 the stack top-to-bottom is [5,1,5]; popMax removes the topmost 5 leaving [1,5], so top() is 1, peekMax() is still 5, pop() removes the 1 leaving [5], and top() is 5.

Example 2:

Input: ops = [push(3), push(7), push(7), push(2), popMax(), popMax(), pop(), top()]

Output: [null,null,null,null,7,7,2,3]

Explanation:

Stack is [3,7,7,2] top-to-bottom. The two 7's tie for max; popMax first removes the higher (more recently pushed) 7, leaving [3,7,2], then the second popMax removes the remaining 7, leaving [3,2]; pop() removes 2 leaving [3], so top() is 3.

Example 3:

Input: ops = [push(4), push(9), pop(), push(1), peekMax(), popMax(), peekMax()]

Output: [null,null,9,null,4,4,1]

Explanation:

After push(4), push(9) the stack is [4,9]; pop() removes 9 leaving [4]; push(1) makes it [4,1]; peekMax() correctly returns 4 (not the removed 9); popMax() removes that 4 leaving [1]; peekMax() then returns 1.

Constraints

• The number of operations is at most 10^4.
• -10^7 <= x <= 10^7 for every value pushed.
• pop, top, peekMax, and popMax are never called on an empty stack.