MaxStack Operations Challenge

Implement a MaxStack data structure that supports the following operations:

• push x: Push the integer x onto the stack.
• pop: Remove and return the element from the top of the stack.
• top: Return the element on the top of the stack.
• peekMax: Retrieve the maximum element in the stack.
• popMax: Retrieve and remove the maximum element in the stack. If there are multiple occurrences of the maximum element, only the top-most one is removed.

You will be given a sequence of commands. The operations that produce output (pop, top, peekMax, popMax) must print their result, each on a new line. Operations that do not require output (such as push) should not print anything.

Note: In your implementation, any necessary formulas or mathematical notations should be written in LaTeX format if applicable.

inputFormat

The first line contains an integer \(n\), representing the number of operations.

Each of the following \(n\) lines describes one operation. The supported operations are:

• push x — Push the integer \(x\) onto the stack.
• pop — Remove and return the top element of the stack.
• top — Return the top element of the stack.
• peekMax — Return the maximum element in the stack.
• popMax — Remove and return the maximum element in the stack.

All input is provided via stdin.

outputFormat

For every operation that returns a value (namely, pop, top, peekMax, and popMax), output the returned value on a new line in the order the operations are executed.

All output should be written to stdout.

## sample

6
push 5
push 1
top
pop
peekMax
popMax

1
1
5
5

</p>