Efficient Stack with Maximum Retrieval

You are required to implement a stack data structure that supports three operations:

• push x: Push an integer x onto the stack.
• pop: Remove the top element from the stack and output it. If the stack is empty, output None.
• max: Output the maximum element currently in the stack in O(1) time. If the stack is empty, output None.

The program will first read an integer n from standard input representing the number of operations. Then, it will read n lines, each describing one of the above operations. For every pop and max operation, output the result on a new line. Operations that do not require output (i.e. push) should produce no output.

Note: Your implementation must ensure that the max operation runs in O(1) time complexity.

The mathematical formulation for the maximum operation is given by:

[ \max(S) = \begin{cases} \max{x : x \in S}, & \text{if } S \neq \emptyset,
\text{None}, & \text{if } S = \emptyset. \end{cases} ]

inputFormat

The first line of input contains an integer n indicating the number of operations. Each of the following n lines contains one of the following commands:

• push x — Push the integer x onto the stack.
• pop — Pop the top element from the stack and print it. If the stack is empty, print None.
• max — Print the maximum element in the stack. If the stack is empty, print None.

outputFormat

For each command pop and max, output the returned value on a separate line in the order they appear in the input. For the push command, do not produce any output.

## sample

6
push 3
max
push 1
max
pop
max

3
3
1
3

</p>