MaxStack Implementation

Implement a stack that supports the following operations in constant time:

• push(x): Push an integer x onto the stack.
• pop(): Remove the element on the top of the stack.
• top(): Get the element on the top of the stack. If the stack is empty, output None.
• max(): Retrieve the maximum element in the stack in O(1) time. If the stack is empty, output None.

You must design your implementation so that all operations run in O(1) time. Internally, you can use an auxiliary data structure to keep track of the maximum element.

The commands will be provided from standard input. Each command is given in a separate line. For commands top and max, print the result to standard output.

Note: The maximum element is defined by the usual integer comparison. If the stack is empty when a top or max command is issued, output None.

inputFormat

The input starts with an integer N representing the number of operations. The following N lines each contain one operation. Each operation can be one of the following forms:

• push x where x is an integer.
• pop
• top
• max

Read input from stdin.

outputFormat

For each top or max operation, print the corresponding result on a separate line to stdout. If the stack is empty when calling top or max, output None.

## sample

10
push 10
push 20
push 30
max
top
pop
max
top
pop
max

30
30
20
20
10

</p>